這道題實際上挺簡單的，果斷的完全背包，只是有一個地方讓我蒙圈了，就是求好幾年以后的收益，后來才知道我勒個去對每一年進行完全背包，然后把這一年的收益加上原來的成本存到下一年中，下一年繼續未完的故事，一直到很多年都完事兒以后，故事就結束了。附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;
}
|