3014 -- Cake Pieces and Plates

POJ

http://acm.pku.edu.cn/JudgeOnline/problem?id=3014


整数 n, m (1 ≦ n, m ≦ 4500) が与えられて，m を n 個の整数の和に何通りに分割できるか答える問題．
ただし答えは非常に大きくなりうるので，答えを 1000000007 で割った余りを出力する．


DP で解いた．
j を i 個の整数の和に分割する方法が dp[i][j] 通りだとすると，

i == 1 のとき

j を 1 個に分割するのは (j) だけなので，dp[1][j] = 1

j == 1 のとき

1 を i 個に分割するのは (0,..,0,1) だけなので dp[i][1] = 1

i < j のとき
  • j を i-1 個に分割し，それに 0 を加えることで j を i 個に分割できるので dp[i-1][j] 通り．
  • i-j を j 個に分割し，それぞれの要素に 1 を加えることで dp[i-1][j-i] 通り．

よって dp[i-1][j] + dp[i][j-i] 通りになる．

例えば i = 2, j = 4 のとき，

  • 4 を 1 個に分割して (4)．これに 0 を加えて (0,4) の 1 通り
  • 2 を 2 個に分割して (0,2), (1,1)．それぞれの要素に 1 を加えて (1,3), (2,2) の 2通り

となる．

i > j のとき

j-i が整数でなくなるので，i < j の1つ目の場合だけ考えればいいので dp[i-1][j] 通り

i == j のとき

i > j の場合に加えて，さらに (1,..,1) という分割があるので dp[i-1][j] + 1 通り


あとはこれらに基づいて計算すればいい．

#include <iostream>
#include <vector>
using namespace std;

int main()
{
  static const int M = 1000000007;
  int n, m;
  cin >> n >> m;

  vector<vector<int> > dp(n, vector<int>(m, 0));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (i == 0 || j == 0) {
        dp[i][j] = 1;
      } else if (i == j) {
        dp[i][j] = (dp[i-1][j] + 1) % M;
      }
      else if (i < j) {
        dp[i][j] = (dp[i-1][j] + dp[i][j-i-1]) % M;
      } else {
        dp[i][j] = dp[i-1][j];
      }
    }
  }
  cout << dp[n-1][m-1] << endl;

  return 0;
}

が，これだと TLE するので dp を int dp[4500][4500] としてグローバルに宣言しておくことで TLE を回避できた．


一度アルゴリズムがわかってしまえばコードは簡単なので C でゴルフもしてみたところ，とりあえず 168B まで縮んだ．