hdu 5000 Clone

dp，用dp[i][j]，表示和为i的前j个维度的种类。其中arr[i]，表示第i维的最大值。

则egin{equation} dp[i][j] = sum_{0 leq k leq min(i,arr[i])} dp[i-k][j-1] end{equation}

最后取和为sum/2的种类即可。原因可参照投n次投骰子，求骰子和的为多少时，概率最大。

代码如下：

 1 #define     MOD 1000000007
 2 #define     MAXN 2002    
 3 #include  <cstdio>
 4 #include  <cstdlib>
 5 #include  <iostream>
 6 #include  <cstring>
 7 using namespace std;
 8 int N;
 9 int arr[MAXN];
10 int dp[MAXN][MAXN];//[sum][dim]
11 int sum;
12 void solve()
13 {
14     memset(dp, 0, sizeof(dp));
15     //init
16     for( int i = 0 ; i < MAXN ; i++ )
17     {
18         dp[0][i] = 1;
19         if( i <= arr[0] )
20         {
21             dp[i][0] = 1;
22         }
23     }
24     for( int j = 1 ; j < N ; j++ )
25     {
26         for( int i = 1 ; i <= sum ; i++ )
27         {
28             int tmp = min(arr[j], i);
29             for( int k = 0 ; k <= tmp; k++ )
30             {
31                 dp[i][j] += dp[i-k][j-1];
32                 dp[i][j] %= MOD;
33             }
34         }
35     }
36     printf ( "%d
", dp[sum/2][N-1] );
37 }
38 int main(int argc, char *argv[])
39 {
40     int T;
41     scanf ( "%d", &T );
42     while(T--)
43     {
44         sum = 0;
45         scanf ( "%d", &N );
46         for( int i = 0 ; i < N ; i++ )
47         {
48             scanf ( "%d", &arr[i] );
49             sum += arr[i];
50         }
51         solve();
52     }
53 }