洛谷 P1853

其实这就是一道完全背包模板题，只不过多了一层n年的循环 dp[k] = max(dp[k], dp[k-a[j][0]/1000]+a[j][1]) 但是注意到题目中写了a是1000的倍数，那么我们可以趁机压缩一下dp空间，可以压缩到 40 * 10 * 1e6 * 1.1^40 / 1000。如果想要再优化的话可以注意一下，每年更新后的的总钱数sum中，小于等于上一年的总钱数lsum的dp[k]，k from 1 to lsum 已经处于最优状态，所以可以直接从sum+1开始dp。（至于第一年lsum=0，直接取max(a[j][0]/1000, lsum+1)就好了）

上代码

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<queue> #include<map> #define ll long long #define pi acos(-1) #define inf 0x3f3f3f3f #define pii pair<int, int> #define mp(a, b) make_pair(a, b) #define piii pair<pii, int> #define min(a, b) (a < b ? a : b) #define max(a, b) (a > b ? a : b) #define uf(a, b, i) for (register int i = (a); i <= (b); ++i) #define df(a, b, i) for (register int i = (a); i >= (b); --i) using namespace std; inline ll read() { ll x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } const int N = 1e6+5; int n, money, t, sum, lsum; int a[11][2]; int dp[N]; int main() { money = read(); n = read(); t = read(); uf(1, t, i) { a[i][0] = read(); a[i][1] = read(); } sum = money/1000; uf(1, n, i) { uf(1, t, j) { uf(max(a[j][0]/1000, lsum+1), sum, k) { dp[k] = max(dp[k], dp[k-a[j][0]/1000]+a[j][1]); } } lsum = sum; money += dp[sum]; sum = money/1000; } printf("%d\n", money); return 0; }