AcWing 1023. 买书
原题链接
简单
作者:
uixva
,
2019-10-04 19:49:22
,
所有人可见
,
阅读 802
/*
这一一个完全背包问题的变种。主要区别在于,钱要刚好用完。
这样对初始化就有一定要求,对于f[0][1~1000],这些情况都是不符合要求的,所以我用-1来做标记
对于f[0~4][0]这些都是符合要求的,初始化为1
*/
#include <iostream>
#include <algorithm>
using namespace std;
int f[5][1010];
int main() {
for (int i = 0; i < 5; ++i) f[i][0] = 1;
for (int j = 1; j < 1010; ++j) f[0][j] = -1;
int c[5];
c[1] = 10;
c[2] = 20;
c[3] = 50;
c[4] = 100;
int n;
while (cin >> n) {
for (int i = 1; i <= 4; ++i) {
for (int j = 1; j <= n; ++j) {
f[i][j] = f[i - 1][j] == -1 ? 0 : f[i - 1][j]; // 验证,上一步是否有解
int k = 1;
while (j - k * c[i] >= 0) {
f[i][j] += f[i - 1][j - k * c[i]] == -1 ? 0 : f[i - 1][j - k * c[i]]; // 验证上一步是否有解
k++;
}
if (f[i][j] == 0) f[i][j] = -1; // 最后验证这一步是否有解
}
}
cout << (f[4][n] == -1 ? 0 : f[4][n]) << endl;
}
return 0;
}