首页 > 代码库 > hdu 5000 Clone
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 //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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。