题目大意：n个数字，上限为maxv，下限0，期间可以加减，问最后最大是多少
一眼看出来是dp，但是考场上tm推错式子了
我的错误式子：
状态：\(f_{i,j}\)表示前i个数字里面进行加操作j次所得到的最大值
转移：\(f_{i,j}=max(f_{i-1,j}-a_i,f_{i-1,j-1}+a_i)\)
显然这是错的，因为有上限，并不满足无后效性。
关于无后效性的解释：
我当前所作出的选择与之后无关，及时我取最大值，但是之后的话可能取最小值会更优
正确的解法：
可达性背包（我自己起的）
状态：\(f_{i,j}\)表示前i个数字是否可以达到j这个大小
转移：\(f_{i,j} =
(f_{i-1,j+a_i},f_{i-1,j-a_i})\)
用第二位维度来表示权值
其实题面已经给了我们提示了：最大上线很小只有\(3e4\)
代码如下：
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
| #include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 3e4 + 6, G = 2e3 + 555;
int n, st, maxv;
int a[N];
bool f[G][N];
signed main()
{
int i, j;
n = read(), st = read(), maxv = read();
for (i = 1; i <= n; ++ i) a[i] = read();
f[0][st] = 1;
for (i = 1; i <= n; ++ i)
{
for (j = 0; j <= maxv; ++ j)
{
if (j + a[i] <= maxv) f[i][j] |= f[i - 1][j + a[i]];
if (j - a[i] >= 0) f[i][j] |= f[i - 1][j - a[i]];
}
}
for (i = maxv; i >= 0; -- i)
{
if (f[n][i])
{
put(i);
fclose(stdin), fclose(stdout);
return 0;
}
}
put(-1);
return 0;
}
|