本文最后更新于：2022年10月27日 晚上
类似最长上升子序列，我们可以推出以下式子：
$\text{dp} = \max{dp_j + 1}, j < i$
并且 a[i] & a[j] 不为 0。（为什么不写进 $\LaTeX$ 呢？因为新博文的并不支持 & 这个东西，一用就挂。）
考虑位运算的特性，每一位并不相关，那么我们可以让 $dp_i$ 表示 二进制下第 i 位为 1 的最大值，这样我们每次找到一个数直接给他二进制拆分，先更新当前最大值，然后拿最大值去更新 dp 数组，这样时间复杂度就变成了 $\mathcal{O}(n \log n)$。
1
2
3
4
5
6
| for(int i = 1; i <= n; ++i) {
int tmp = 1;
for(int j = 0; j < 64; ++j) if((a[i] >> j) & 1) tmp = max(dp[j] + 1, tmp);
for(int j = 0; j < 64; ++j) if((a[i] >> j) & 1) dp[j] = max(dp[j], tmp);
ans = max(ans, tmp);
}
|
不是很方便知道具体的边长，那么我们就转换思路为看能否圈出 a，b，c 长度的三条边。
则 $dp_{a, b, c}$ 表示能否围成 a，b，c 三条边。
一算空间爆掉了，想办法优化。
因为周长已知，那么我们只需要知道两条边即可推出第三边，那么我们就可以优化成：
$$dp_{i, j, k}$$ 表示第 i 个点，长度为 j，k 两条边能否围成。
经过研究可以发现，我们可以直接原地滚动数组，第一维直接省略掉，转化为。
考虑状态转移方程：
- 如果我们将当前边放到 j 处，则我们需要通过 $dp_{j - a_i, k}$ 推过来。
- 如果我们将当前边放到 k 处，则我们需要通过 $dp_{j, k - a_i}$ 推过来。
- 如果我们将当前边放到第三条边，我们只需要 $dp_{j, k}$ 推过来。
那么状态转移方程为：$dp_{i, j} |= (dp_{i - a_k, j}, dp_{i, j - a_k})$
现在我们已知了可以到达的边，去枚举这些边，然后判断是否可以凑出这三条边，再看能否围成三角形，最后统计答案输出即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| dp[0][0] = true;
for(int i = 1; i <= n; ++i)
for(int j = sum >> 1; j >= 0; --j)
for(int k = sum >> 1; k >= 0; --k) {
if(j >= a[i]) dp[j][k] |= dp[j - a[i]][k];
if(k >= a[i]) dp[j][k] |= dp[j][k - a[i]];
}
double ans = -1;
for(int i = sum; i > 0; --i)
for(int j = sum; j > 0; --j) {
if(!dp[i][j]) continue;
if(!is_ok(i, j, sum - i - j)) continue;
ans = max(ans, calc(i, j, sum - i - j));
}
|
首先分析题意，可以得出线性 DP。
一维肯定不够，我们需要知道上一个子问题状态选择了哪一棵树，因此加上一维，这样最初的状态就变成了：$dp_{i, \ 0/1/2}$，表示到了第 i 个位置，放高度为 10，高度为 1，高度为 2 的树的最大收益。
坑人的是，我们依旧无法转移，因为我们没办法知道这个树是比左右都低还是比左右都高。
那就，再塞进去一维！
现在变成了：$dp_{i, \ 0/1/2, \ 0/1}$ 表示第 i 个位置，放高度为 10，高度为 1，高度为 2 的树，并且当前的树比左右两边都矮或比左右两边都高的最大收益。
现在好像可以做了，我们推一下状态转移方程：
$$dp_{i, 0, 0} = \max{dp_{i-1, 1, 1}, dp_{i - 1, 2, 1}} + a[i]$$
$$dp_{i, 1, 0} = dp_{i - 1, 2, 1} +b[i]$$
$$dp_{i, 1, 1} = dp_{i - 1, 0, 0} + b[i]$$
$$dp_{i, 2, 1} = \max{dp_{i - 1, 0, 0},\ dp_{i - 1, 1, 0}} + c[i]$$
考虑一下初始化，直接设成 0 就可以了。
最后答案枚举最后一颗树的种类状态即可。
来一波操作：
1
2
3
4
5
6
7
8
9
10
11
12
| for(int i = 1; i <= n; ++i) {
dp[i][0][0] = max(dp[i - 1][1][1], dp[i - 1][2][1]) + a[i];
dp[i][1][0] = dp[i - 1][2][1] + b[i];
dp[i][1][1] = dp[i - 1][0][0] + b[i];
dp[i][2][1] = max(dp[i - 1][0][0], dp[i - 1][1][0]) + c[i];
}
int ans = 0;
for(int i = 0; i < 3; ++i)
for(int j = 0; j < 2; ++j)
ans = max(ans, dp[n][i][j]);
|
然后我们壮烈地牺牲了 30 pts。
分析一下原因我们发现，我们未能正确处理好最后一棵树和第一颗树的关系，因此导致了 WA。
那我们就不得不换种思路：先枚举第一颗树的状态，然后以这个状态为基础去更新接下来的位置，然后在更新的途中就把最大值取了。
现在我们过了：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| for(int j = 0; j < 3; ++j) {
for(int i = 0; i < 3; ++i)
for(int k = 0; k < 2; ++k)
dp[1][i][k] = 0;
if(j == 0) dp[1][j][0] = dp[1][j][1] = a[1];
else if(j == 1) dp[1][j][0] = dp[1][j][1] = b[1];
else if(j == 2) dp[1][j][0] = dp[1][j][1] = c[1];
for(int i = 2; i <= n; ++i) {
dp[i][0][0] = max(dp[i - 1][1][1], dp[i - 1][2][1]) + a[i];
dp[i][1][0] = dp[i - 1][2][1] + b[i];
dp[i][1][1] = dp[i - 1][0][0] + b[i];
dp[i][2][1] = max(dp[i - 1][0][0], dp[i - 1][1][0]) + c[i];
}
for(int i = 0; i < j; ++i) ans = max(ans, dp[n][i][0]);
for(int i = 2; i > j; --i) ans = max(ans, dp[n][i][1]);
}
|
一眼多重背包，上去先来个朴素的解法，成功过了样例，然后 TLE 了。
朴素
首先可以看出这是个多重背包，那么我们就可以将每一个物品分出来，按照 01 背包那么折腾，这样时间复杂度是 $\mathcal{O(m\sum_{i=1}^{n}c_i)}$ ，毫无疑问地去世。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| while(n = rd(), m = rd()) {
if(n == 0 && m == 0) break;
for(int i = 1; i <= n; ++i) a[i] = rd();
for(int i = 1; i <= n; ++i) c[i] = rd();
memset(dp, 0, sizeof(dp));
dp[0] = 1;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= c[i]; ++j)
for(int k = m; k >= a[i]; --k)
dp[k] |= dp[k - a[i]];
int ans = 0;
for(int i = 1; i <= m; ++i)
ans += dp[i];
printf("%d\n", ans);
}
|
二进制拆分
既然朴素的没辙，那我们就玩一下之前学过的二进制拆分来优化一下这个东西。
但是这样的时间复杂度是 $\mathcal{O(m\sum_{i=1}^{n}\log{c_i})}$，但是数据实在是太强大了，依旧超时。
不过至少能优化掉一大片吧……
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
| while(n = rd(), m = rd()) {
if(n == 0 && m == 0) break;
for(int i = 1; i <= n; ++i) a[i] = rd();
for(int i = 1; i <= n; ++i) c[i] = rd();
int tot = 0;
memset(b, 0, sizeof(b));
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= c[i]; j <<= 1) {
b[++tot] = j * a[i];
c[i] -= j;
}
if(c[i]) b[++tot] = a[i] * c[i];
}
memset(dp, 0, sizeof(dp));
dp[0] = 1;
for(int i = 1; i <= tot; ++i)
for(int j = m; j >= b[i]; --j)
dp[j] |= dp[j - b[i]];
int ans = 0;
for(int i = 1; i <= m; ++i)
ans += dp[i];
printf("%d\n", ans);
}
|
贪心
注意啊，这里只是在怎么决策的时候贪心了一下，整体上还是 DP。
我们发现一个奇妙的性质：这题我们只要可行性就好了，不需要最优性。
既然如此，如果前 i 种硬币能拼成 j，只有两种可能：
- j 早就被拼出来了。
- 用一下第 i 种硬币拼成 j。
很明显，我们能用 1 解决的就不用 2 解决。这样我们设一个 $used_j$ 表示让 $dp_j$ 在 i 阶段时为 true 至少需要多少种第 i 枚硬币，能用 1 就用1，并且将 $used_j$ 设成 0，这时候不需要第 i 种硬币来解决问题。
否则，考虑用当前硬币解决问题，退回到上一个状态，看一下那个状态耗费的第 i 种硬币数是否比给定的数量少，如果少的话并且那个状态已经拼出来了，我们就转移，否则就……
终于，时间复杂度被我们弄成了 $\mathcal{O(nm)}$，总算是过了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| while(n = rd(), m = rd()) {
if(n == 0 && m == 0) break;
for(int i = 1; i <= n; ++i) a[i] = rd();
for(int i = 1; i <= n; ++i) c[i] = rd();
memset(dp, 0, sizeof(dp));
dp[0] = 1;
for(int i = 1; i <= n; ++i) {
for(int j = 0; j <= m; ++j) used[j] = 0;
for(int j = a[i]; j <= m; ++j)
if(!dp[j] && dp[j - a[i]] && used[j - a[i]] < c[i])
dp[j] = true, used[j] = used[j - a[i]] + 1;
}
int ans = 0;
for(int i = 1; i <= m; ++i)
ans += dp[i];
printf("%d\n", ans);
}
|
线性 DP，我们先来分析一下状态，很明显，我们可以将当前路径的长度作为状态。
我们依然需要知道当前的末尾位置，因此我们还要想方设法地折腾出表示两个末尾位置的方法。
经过仔细的分析我们发现：我们走过的路径 $i$，和两个末尾节点的坐标 $x1, y1$， $x2, y2$ 的关系是这样的：
$i + 2 = x1 + y1 = x2 + y2$
注意，初始点的位置并不算进经过的路径中。
那么我们现在就可以用三个状态推知剩下的两个状态了：
$$y1 = i + 2 - x1, y2 = i + 2 - x2$$
这样一来我们就可以通过枚举三个维度，从而得到另外两个维度的信息。
设：$dp_{i, x1, x2}$ 表示路径长度为 i，一条路径的末节点的横坐标为 x1，另一条为 x2。
考虑 $x1 = x2$ 的转移：
如果当前 $x1 = x2$，那么向下走的时候会走到同一个节点上，那么我们就只能取一次值：$dp_{i + 1, x1 + 1, x2 + 1} = \max{dp_{i + 1, x1 + 1, x2 + 1}, dp_{i, x1, x2} + a_{x1, y1 + 1}}$
如果当前 $x1 = x2$，那么向右走的时候也会走到同一个节点上，同理：$dp_{i + 1, x1, x2} = \max{dp_{i + 1, x1, x2}, dp_{i, x1, x2} + a_{x1 + 1, y1}}$
当 $x1 = x2 + 1$ 或 $x2 =x1 + 1$
这时候向下走就要考虑一下了，因为一个节点会走到曾经取走过的节点上，这时候我们就要考虑一下向下更新的问题了。如果 $x1 + 1 = x2$，说明 x1 在 x2 的斜右上边，这时候我们先让 x1 走到与 x2 相同的位置上，此时我们只能够取到 $a_{x1 + 1, y1}$ 的位置上的价值（如果看不懂可以自行画图理解）。
第二种情况同理呦。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| for(int i = 0; i < n + m - 2; ++i)
for(int x1 = 1; x1 <= n && x1 <= i + 1; ++x1)
for(int x2 = 1; x2 <= n && x2 <= i + 1; ++x2) {
int y1 = i - x1 + 2, y2 = i - x2 + 2;
if(x1 == x2) {
dp[i + 1][x1][x2] = max(dp[i + 1][x1][x2], dp[i][x1][x2] + a[x1][y1 + 1]);
dp[i + 1][x1 + 1][x2 + 1] = max(dp[i + 1][x1 + 1][x2 + 1], dp[i][x1][x2] + a[x1 + 1][y1]);
} else {
dp[i + 1][x1][x2] = max(dp[i + 1][x1][x2], dp[i][x1][x2] + a[x1][y1 + 1] + a[x2][y2 + 1]);
dp[i + 1][x1 + 1][x2 + 1] = max(dp[i + 1][x1 + 1][x2 + 1], dp[i][x1][x2] + a[x1 + 1][y1] + a[x2 + 1][y2]);
}
if(x1 + 1 == x2) dp[i + 1][x1 + 1][x2] = max(dp[i + 1][x1 + 1][x2], dp[i][x1][x2] + a[x1 + 1][y1]);
else dp[i + 1][x1 + 1][x2] = max(dp[i + 1][x1 + 1][x2], dp[i][x1][x2] + a[x1 + 1][y1] + a[x2][y2 + 1]);
if(x2 + 1 == x1) dp[i + 1][x1][x2 + 1] = max(dp[i + 1][x1][x2 + 1], dp[i][x1][x2] + a[x1][y1 + 1]);
else dp[i + 1][x1][x2 + 1] = max(dp[i + 1][x1][x2 + 1], dp[i][x1][x2] + a[x1][y1 + 1] + a[x2 + 1][y2]);
}
|
哇，上来这题弄得人毫无思路。
仔细瞅了瞅发现是个分组背包。
先想一个问题：派出的部队人数肯定严格大于对面的人数加 1，不然就是去白给，白给是肯定不能接受的。
那么，如何确定派出部队的方法呢？
观察到题目中派出部队的方法是相对于每一个阵地而言的，这样一来我们就可以按照每个阵地的角度上去思考，而不是从每个对手的角度去思考。
那么，我们就可以把到了哪一个阵地作为阶段，注意到剩余的部队人数也是一个不可或缺的附加维度，那么我们就应该将其也加入到状态中。
设 $dp_{i, j}$ 表示到了第 i 个阵地，还剩下 j 部队人数的最大受益值。
注意到第一维可以直接原地滚动数组秒掉，注意循环顺序，别无中生部队啊。
怎样更好地确定向每个阵地派出多少部队呢？
发现每个阵地上驻守的人数是无序的，也就是说是不好处理的，既然如此我们就把每个阵地上的人数升序排序，这样一来如果我们当前的部队人数能够击败第 k 个对手的，之前的对手肯定也都是可以击败的，这样一来我们就可以较为方便地处理向每个阵地派出的部队人数了。
这样方便了转移也方便了设计方程。
因为我们使用了滚动数组，转移时一定要注意先枚举部队人数然后再枚举每一个对手。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| for(int i = 1; i <= s; ++i)
for(int j = 1; j <= n; ++j)
a[j][i] = rd();
for(int i = 1; i <= n; ++i)
sort(a[i] + 1, a[i] + 1 + s);
for(int i = 1; i <= n; ++i)
for(int j = m; j >= 0; --j)
for(int k = 1; k <= s; ++k)
if(j > 2 * a[i][k])
dp[j] = max(dp[j - a[i][k] * 2 - 1] + k * i, dp[j]);
printf("%d", dp[m]);
|