首页 > 代码库 > openjudge-NOI 2.6-2985 数字组合
openjudge-NOI 2.6-2985 数字组合
题目链接:http://noi.openjudge.cn/ch0206/2985/
题解:
跟背包问题有点相似,暂且算背包型DP吧,虽然是一道递推题……
fj表示和为j时的结果,得:
即为j减去每一个数的情况
(word的公式编辑好好用……)
[ATTENTION]和背包问题相似的一点是,第二层循环j要倒序
1 #include<cstdio> 2 int n,m,v[21],f[1010]; 3 inline int max(int x,int y) 4 { 5 return x>y?x:y; 6 } 7 int main() 8 { 9 scanf("%d%d",&n,&m); 10 for(int i=1;i<=n;++i)scanf("%d",&v[i]); 11 f[0]=1; 12 for(int i=1;i<=n;++i) 13 for(int j=m;j>=v[i];--j) 14 f[j]+=f[j-v[i]]; 15 printf("%d",f[m]); 16 return 0; 17 }
openjudge-NOI 2.6-2985 数字组合
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。