洛谷P2347 砝码称重 某一年noip提高组原题

可以转化为01背包求方案数的问题，dp数组f[][]表示第几个砝码能称出的重量,可压缩至一维 转移方程为f(i,j)+=f(i-1,j-w[i]) 当前我们可以称出的重量必定是由之前的砝码重量转移过来的

#include<bits/stdc++.h> using namespace std; const int N=550; const int maxn=1e6+7; int f[maxn]; int a[maxn]; int v[maxn];//相当于01背包的物品重量 int num[10]={0,1,2,3,5,10,20};//砝码重量 int cnt; int maxsum; int ans; int main() {for(int i=1;i<=6;i++){scanf("%d",&a[i]);for(int j=1;j<=a[i];j++){v[++cnt]=num[i];//统计 }}for(int i=1;i<=cnt;i++){maxsum+=v[i];//背包的最大容量 }f[0]=1;//0也是一种方案，初始状态for(int i=1;i<=cnt;i++)//01背包 {for(int j=maxsum;j>=v[i];j--){f[j]+=f[j-v[i]];}}for(int i=1;i<=maxsum;i++)//统计方案个数 {if(f[i]){ans++;}}printf("Total=%d",ans);return 0; }

 

转载于:https://www.cnblogs.com/LJB666/p/10808631.html

总结

以上是生活随笔为你收集整理的洛谷P2347 砝码称重 某一年noip提高组原题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。