总time limit 336010000 msmemorylimit 336065536 kb description有一个魔法口袋，总容积为40，用这个口袋可以改变什么。 这些项目的总体积必须为40。 约翰现在有n个想得到的物品。 各个道具的体积分别为a 1、a 2……a n。 John可以在这些物品中选择一些。 如果选择的物体总体积为40，利用这个神奇的口袋，John可以得到这些物品。 现在的问题是，John有几种不同的项目选择方法？ 输入的第一行是正整数n(1=n=20 )，表示不同的项目数。 以下n行每行都有1到40的正整数，分别给出a 1、a 2……a n的值。 Output输出不同的项目选择方法的数量。 样品输入3202020样品输出3
这个题有点像背包的思想；
要求可以满足要求的次数；样例是1 3 ；2 3 ； 1 2 ；三种刚好满足40；
讨论状态 （选 或者 不选） ；
针对DP[i][j] 就为满足重量i选择的前j种商品的方法；
所以初始状态 dp[0][j] (j=0j=n) == 1 ； （每个商品都考虑不选，则都有1种）；
所以如果上个状态不选择j物品， 则 dp[i][j] = dp[i][j-1];
3358 www.Sina.com/http://www.Sina.com/DP [ I ] [ j ]=DP [ I-a [ j ] [ j-1 ]；
如果满足 i - a[j] = 0 , 就选择这个
# include iostream # include bits/stdc.husingnamespacestd； int a[30]； int n； int dp[40][30]； //dp[i][j]是从前面j种物品取出体积I的方法的数量int main () {cin n； memset(DP，0，sizeof ) DP )； for(intI=1； i=n； I () {cin a[i]； dp[0][i]=1； }dp[0][0]=1； for(intI=1； i=40； I ) for(intj=1； j=n； j({DP[I][j]=DP[I][j-1]； if(I-a(j )=0) DP ) I ) ) j )=DP ) I-a ) ) j-1 )； }}cout dp[40][n]endl； 返回0； }