hdu 5000 Clone

dp, dp[i][j]로 i의 전 j차원의 종류를 나타낸다.그 중에서arr[i]는 i차원의 최대치를 나타낸다.
그러면\begin{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 }