cafelier@SRM

SRM459 500

あとで | 03:46 |

• 改めて清書し直してみると綺麗に書けるものだなあ。
• この手のDPを線形時間で書くのが苦手なので克服しなければ。
  • このパターンが苦手であるとはっきり認識できたのでよかった
  • 次は迷わず解く

class NumberPyramids { public:
   int count(int baseLength, int top) 
   {
      const int n = baseLength-1;
      const int s = top - (1<<n);
      if( s<0 || n>20 )
         return 0;

      vector<int> dp(s+1, 0);
      dp[0] = 1;

      for(int i=0, nCi=1; i<=n; ++i, nCi=nCi*(n-i+1)/i)
         for(int x=nCi; x<=s; ++x)
            (dp[x] += dp[x-nCi]) %= 1000000009;

      return dp[s];
   }
};