首页 > 代码库 > hdu 5000 Clone

hdu 5000 Clone

2024-07-25 02:40:31   219人阅读

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     //init16     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\n", 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 }

 

hdu 5000 Clone


联系
我们