这道题实际上挺简单的，果断的完全背包，只是有一个地方让我蒙圈了，就是求好几年以后的收益，后来才知道我勒个去对每一年进行完全背包，然后把这一年的收益加上原来的成本存到下一年中，下一年继续未完的故事，一直到很多年都完事儿以后，故事就结束了。附AC代码   view code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define maxl 200000
int max(int a, int b)
{
if (a > b) return a;
else return b;
}
int main()
{
int n, k, now, y, v, p, t, x, c[20], w[20], dp[maxl], i, j;
cin >> t;
for (x = 1; x <= t; x++)
{
cin >> v >> y;
cin >> n;
for (i = 1; i <= n; i++)
{
cin >> c[i] >> w[i];
c[i] /= 1000;
}
now = 0;
for (k = 1; k <= y; k++)
{
v += now;
p = v / 1000;
memset(dp, 0, sizeof(dp));
for (i = 1; i <= n; i++)
for (j = c[i]; j <= p; j++)
dp[j] = max(dp[j], dp[j - c[i]] + w[i]);
now = dp[p];
}
v += now;
cout << v << endl;
}
return 0;
}
|