首页 > 代码库 > 【noi 2.6_6049】买书（DP）
【noi 2.6_6049】买书（DP）
题意：有N元，有无限多本10、20、50和100元的书，问有几种购买方案。
解法：f[i]表示用 i 元的方案数。还有一个 j 循环这次买多少元的书。
注意——要先 j 循环，再 i 循环。因为要先考虑第一种书，再是下一种书。若先 i 循环，后 j 循环，则相同的购买方案由购买次序不同而重复计算。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 using namespace std; 6 7 const int N=1010; 8 int f[N],e[4]={10,20,50,100}; 9 10 int main()11 {12 int n;13 scanf("%d",&n);14 memset(f,0,sizeof(f));15 f[0]=1;16 for (int j=0;j<4;j++)17 for (int i=10;i<=n;i+=10)18 if (i>=e[j]) f[i]+=f[i-e[j]];19 printf("%d\n",f[n]);20 return 0;21 }
【noi 2.6_6049】买书（DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。