1 条题解
-
1
//主要想法就是先判断可以转换成哪一种背包来做还是说可以方便发现其中的递推式子。发现转换成01背包更简单后就进行接下来的无脑操作啦(主要因为一个砝码取和不取分为两种情况,而一个砝码又有多个,所以也可以变为多重背包来求解) //上本蒟蒻代码(学长们嘴下留情)// //相同质量的多个砝码拆解后就相当于多个相同质量的物品 //f[n]表示用第n个时所能称出的重量总数 ,将每个拆开来变为标准01背包基题 //其实大暴力好像也能过
#include<bits/stdc++.h> #define ll long long using namespace std; const int TNT = 1e8+99,xy = 5005; int n , m; int a[TNT]; int f[TNT];
int main(){ int b[7] = {0 , 1, 2, 3, 5, 10, 20}; int i = 0; int tot = 0; while(cin >> n){ i++;
for(int j = 1; j <= n; j++) a[++tot] = b[i]; } f[0] = 1; for(int i = 1; i <= tot; i++) for(int j = 1000; j >= 1; j--){ f[j] = f[j] + f[j - a[i]]; } int ans = 0; for(int i = 1; i <= 1001; i++) { if(f[i]) ans ++; } cout << "Total=" << ans; return 0;
}
- 1
信息
- ID
- 349
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 7
- 标签
- 递交数
- 65
- 已通过
- 13
- 上传者