(TIOJ) 1973 . 分群問題（Partition） [球球DP(?)]

http://tioj.infor.org/problems/1973

第一次成功克服心理恐懼，寫出類似這種的DP式子><

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const LL mod = 1e9 +7;

const int N = 5006;

int dp[N][N];

int main ()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    char c;
    cin >> c;
    if (c=='U')
    {
        int n,k;
        cin >> n >> k;
        while (k--)
        {
            int x;
            cin >> x;
            n-=x;
        }
        dp[0][0] = 1;
        //i balls has j boxes
        for (int i=1;n>=i;i++)
        {
            for (int j=1;i>=j;j++)
            {
                if (i-j < 0) dp[i][j] = dp[i-1][j-1];
                else dp[i][j] = dp[i-1][j-1] + dp[i-j][j];
                dp[i][j] %= mod;
                //cout<<dp[i][j]<< ' ';
            }
            //cout<<endl;
        }
        LL sum = 0;
        for (int i=1;n>=i;i++)
        {
            sum += dp[n][i];
            sum %= mod;
        }
        cout << sum << endl;
    }
    else {
        int n,k;
        cin >> n >> k;
        dp[k][k] = 1;
        //i balls has j boxes
        for (int i=k;n>=i;i++)
        {
            for (int j=k;i>=j;j++)
            {
                if (i==k && j==k) continue;
                dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]*1LL*j ) % mod;
                dp[i][j] %= mod;
            }
        }
        LL sum=0;
        for (int i=1;n>=i;i++)
        {
            sum += dp[n][i];
            sum %= mod;
        }
        cout << sum << endl;
    }
}