题意
usiness
题意也有点费解。给你一个递减函数，表示今天x元可以在下一天得到$f(x)$元。然后每天都可以任意选方案，花费当天的钱，来获得最后的钱。不过保证一定是不会有赚的。
问最后一天得到的钱的最大值。
思路
我思考了很久，因为收益会递减，所以其实每天拿在手头的钱其实不会很多（数据范围1000，实测2000多足够）。
所以我后来瞎捣鼓出这样的做法：
枚举第$i$天，枚举当天手头有$x$元钱，然后枚举这$x$元钱有j元是做完美投资的，然后转移得到得到最大的最后收到收益（不算手头的钱，所以最后还要加上手头的）。
完美投资是指，这$j$元钱完全花光能拿到的最大收益，所以我预处理了一个完全背包。但是奇怪的点在于，这背包要么就是完全能被占满，要么就全空。（也就是只从0转移来状态）
转移方程看起来很飘，其实意思很简单，因为第二维是下一天刚开始手头有的钱，所以我吧各种剩余和f都叠在一起算了，导致看起来非常崩坏。
$lt[x]$数组看起来很奇怪，我本意是想表示当前x的钱做完全背包后剩余的钱，但是我发现最后改成x必须正好花光才可以转移。导致$lt[x]$要么等于0，要么等于x了。
我是最后瞎改那个变成完美投资才过的，我也不懂为什么。我中间因为做了判复数的情况，剪掉了很多状态，所以虽然复杂度好像似乎$O(nkk)$的，但很接近$O(nmk) $
看了nikkukun 巨巨的代码，我觉得我在写弟弟代码。
他说这就是一个负权背包的问题（？
主要和我不一样的点在于，他把隔天领钱这一步单独拎出来转移了（比我瞎搞半天求和好）
然后从大到小枚举当前的收益能转移给那些状态，非常合理，我稍微改一点就wa爆。
然后我就不知道如何思考这题了，到现在我还是有很懵逼的点，或许我应该做做负权背包。
代码
我的奇怪做法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
|
#include <bits/stdc++.h>
#define _debug(x) cerr<<#x << " = " << x<<endl
using namespace std;
typedef long long ll;
const int MOD = -1;
const double eps = 1e-3;
const int MAXN = 2e3 + 59;
const ll INF = 0x3f3f3f3f3f3f;
int kase;
int n, m, k;
ll ans;
ll f[MAXN];
ll a[MAXN], b[MAXN];
ll dp[105][MAXN];
ll bg[MAXN];
ll lf[MAXN];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> k;
for (int i = 0; i <= k; ++i) {
cin >> f[i];
}
for (int i = 1; i <= m; ++i) {
cin >> a[i] >> b[i];
}
for (int x = 1; x < MAXN; ++x)
bg[x] = -INF, lf[x] = x;
for (int j = 1; j <= m; ++j) {
for (int x = a[j]; x < MAXN; ++x) {
if (bg[x] < bg[x - a[j]] + b[j]) {
bg[x] = bg[x - a[j]] + b[j];
lf[x] = lf[x - a[j]];
}
}
}
for (int i = 0; i <= n + 2; ++i)
for (int x = 0; x < MAXN; ++x)
dp[i][x] = -INF;
dp[0][0] = 0;
for (int i = 0; i <= n; ++i) {
for (int x = 0; x < MAXN; ++x) {
if (dp[i][x] < 0)continue;
for (int j = 0; j <= x; ++j) {
if (bg[j] < 0)continue;
dp[i + 1][lf[j] + x - j + f[lf[j] + x - j]] =
max(dp[i + 1][lf[j] + x - j + f[lf[j] + x - j]],
dp[i][x] + bg[j]);
}
}
}
for (int l = 0; l < MAXN; ++l) {
ans = max(ans, dp[n][l] + l);
}
cout << ans << endl;
return 0;
}
|
nikkukun 的优秀做法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef pair<int, int> pint;
const int N = 100 + 5, K = 2000 + 5;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
ll g[N][K];
int f[K], a[N], b[N];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m, upp;
cin >> n >> m >> upp;
for (int i = 0; i <= upp; i++)
cin >> f[i];
for (int i = 1; i <= m; i++)
cin >> a[i] >> b[i];
for (int i = 1; i <= n + 1; i++)
for (int j = 0; j < K; j++)
g[i][j] = -INF_LL;
g[1][0] = 0;
for (int i = 2; i <= n + 1; i++) {
for (int j = 0; j < K; j++)
g[i][j + f[j]] = max(g[i][j + f[j]], g[i - 1][j]);
for (int j = K - 1; j >= 0; j--)
for (int k = 1; k <= m; k++) {
if (j - a[k] < 0) continue;
g[i][j - a[k]] = max(g[i][j - a[k]], g[i][j] + b[k]);
}
}
ll ans = 0;
for (int j = 0; j < K; j++)
ans = max(ans, j + g[n + 1][j]);
cout << ans;
return 0;
}
|
