题目链接
洛谷 P2347 [NOIP 1996 提高组] 砝码称重
思路分析
这题其实就是有 \(6\) 件物品的多重背包，把其朴素版本复制 \(6\) 份即可。
代码呈现
#include<bits/stdc++.h>
using namespace std;const int N=1010;
int a1,a2,a3,a4,a5,a6;
bool dp[N];int main(){scanf("%d%d%d%d%d%d",&a1,&a2,&a3,&a4,&a5,&a6);int s=a1+2*a2+3*a3+5*a4+10*a5+20*a6;dp[0]=1;for (int i=1;i<=a1;++i){for (int j=s;j>=i;--j) dp[j]|=dp[j-i];}for (int i=1;i<=a2;++i){for (int j=s;j>=2*i;--j) dp[j]|=dp[j-2*i];}for (int i=1;i<=a3;++i){for (int j=s;j>=3*i;--j) dp[j]|=dp[j-3*i];}for (int i=1;i<=a4;++i){for (int j=s;j>=5*i;--j) dp[j]|=dp[j-5*i];}for (int i=1;i<=a5;++i){for (int j=s;j>=10*i;--j) dp[j]|=dp[j-10*i];}for (int i=1;i<=a6;++i){for (int j=s;j>=20*i;--j) dp[j]|=dp[j-20*i];}int cnt=0;for (int i=1;i<=s;++i){if (dp[i]) ++cnt; }printf("Total=%d",cnt);return 0;
}