Description
有一个含 \(n\) 个点的链，每个点有一个权值。
对于任何 \(1\le i\le n-1\)，都有一条边连接 \((i,i+1)\)。
您可以在链中的任意一些节点放置一些生物。
对于第 \(i\) 条边，若点 \(i\) 至少有 \(a_i\) 个生物或点 \(i+1\) 至少有 \(b_i\) 生物，则该边可以打开。
链是有出口的，如果在 \(1\) 号点有 \(m\) 个生物，则出口会被打开。
您要确定，至多放置多少个生物，可以使得生物不会打开出口。
打开了不一定能走过去。
\(1\le n\le 10^3\)，\(1\le m,a_i,b_i\le 10^4\)。
Solution
先考虑已知初始每个节点上的生物数量，对于每个位置如何最大化其上面的生物数量。
注意到操作可逆，所以可以先让对于每个节点从左往右，去让其上的生物尽可能多的往右走。再从右往左让生物尽可能往左走，这么一直先右后左地走很多轮，最后一次往左时走到 \(i\) 号点时 \(i\) 上的生物数量就是这个位置可能的最大生物数量。
由于限制条件是终止状态下 \(1\) 号点上的生物数量，所以如果直接对初始状态每个点上的生物数量做的话会很难刻画最终状态。又因为最终状态下再做一次先右后左后整个状态不会变，所以考虑直接对最终状态 dp。
设 \(c_i\) 表示最终状态下第 \(i\) 个点的生物数量，即做很多次先右后左后的结果，\(s_i\) 表示第 \(i\) 个点可能的最大生物数量，注意 \(c_i\) 不等于 \(s_i\)。
显然 \(c_1=s_1\)。同时对于每个 \(i(i>1)\)，向右第一次推到 \(i\) 和向左第一次推到 \(i\) 时 \(i\) 上的数量为 \(s_i\)，向右到 \(i+1\) 以及向左到 \(i-1\) 时 \(i\) 上的数量为 \(c_i\)。然后进行分讨：
-
\(s_i\geq a_i+b_i\)：
向右从 \(i\) 推到 \(i+1\) 时 \(i\) 上的 \(s_i\) 个生物显然能够全部到 \(i+1\)，所以 \(s_{i+1}\geq s_i\)。向左从 \(i+1\) 推到 \(i\) 时 \(i+1\) 上的 \(s_{i+1}\) 个生物同样能够全都回 \(i\)，所以 \(s_{i}\geq s_{i+1}\)。
由于 \(i\) 推到 \(i+1\) 时如果 \(c_{i+1}\neq 0\)，就会得到 \(s_{i+1}\geq c_{i+1}+s_i>s_i\)，矛盾。所以 \(c_{i+1}=0\)。
-
\(a_i\leq s_i<a_i+b_i\)：
向右从 \(i\) 推到 \(i+1\) 后 \(i\) 会剩下 \(a_i\)，而 \(i+1\) 会变为 \(c_{i+1}+s_i-a_i\)，所以 \(s_{i+1}\geq c_{i+1}+s_i-a_i\)。再从 \(i+1\) 推回 \(i\) 时，\(i\) 能够将 \(i+1\) 上的生物全吸过去，所以 \(s_i\geq a_i+s_{i+1}\geq c_{i+1}+s_i\)。
容易得到 \(c_{i+1}=0,s_{i+1}=s_i-a_i\)。
-
\(0\leq s_i<a_i\)：
这个时候就要讨论 \(i+1\) 能否推回 \(i\) 了。
-
\(s_{i+1}\geq b_i\)：
如果 \(s_{i+1}\geq a_i+b_i\)，\(s_i\) 就必须等于 \(s_{i+1}\)，与 \(s_i<a_i\) 矛盾，所以 \(s_{i+1}<a_i+b_i\)。
显然 \(i\) 推不到 \(i+1\)。从 \(i+1\) 推回 \(i\) 前，\(i\) 上只能剩下 \(0\) 个生物，否则 \(i+1\) 会吸过去让 \(s_{i+1}\) 更大。从 \(i+1\) 推回 \(i\) 后，\(i+1\) 会剩下 \(b_i\)，\(i\) 会得到 \(s_{i+1}-b_i\)。
所以 \(c_{i+1}=b_i,s_{i+1}=s_{i}+b_i\)。
-
\(0\leq s_{i+1}<b_i\)：
\(i\) 和 \(i+1\) 无法互通，所以只需要满足 \(s_{i+1}=c_{i+1}\)。
-
考虑根据上面的东西进行 dp，设 \(f_{i,j}\) 表示考虑了 \([1,i]\) 的 \(s\) 和 \(c\)，钦定 \(s_i=j\) 时 \(\max_{j=1}^{i}c_j\) 的最大值，初始状态是 \(f_{1,j}=j(0\leq j<m)\)，可以得到转移：
直接转移即可，最终结果是 \(f_{n,*}\) 的最大值。
时间复杂度：\(O(nV)\)。
Code
#include <bits/stdc++.h>// #define int int64_tconst int kMaxN = 2e3 + 5, kMaxM = 4e4 + 5;int cid, n, m, lim;
int a[kMaxN], b[kMaxN], f[2][kMaxM];inline void chkmax(int &x, int y) { x = (x > y ? x : y); }
inline void chkmin(int &x, int y) { x = (x < y ? x : y); }void dickdreamer() {std::cin >> n >> m;lim = m;for (int i = 1; i < n; ++i) std::cin >> a[i] >> b[i], lim = std::max({lim, a[i], b[i]});lim *= 2;int o = 0;std::fill_n(f[o], lim + 1, -1e9);for (int i = 0; i < m; ++i) f[o][i] = i;for (int i = 1; i < n; ++i) {o ^= 1;std::fill_n(f[o], lim + 1, -1e9);int mx = -1e9;for (int j = 0; j <= lim; ++j) {if (j >= a[i] + b[i]) {chkmax(f[o][j], f[o ^ 1][j]);} else if (j >= a[i]) {chkmax(f[o][j - a[i]], f[o ^ 1][j]);} else {chkmax(f[o][j + b[i]], f[o ^ 1][j] + b[i]);chkmax(mx, f[o ^ 1][j]);}}for (int j = 0; j < b[i]; ++j) chkmax(f[o][j], mx + j);}int ans = -1e9;for (int i = 0; i <= lim; ++i) chkmax(ans, f[o][i]);std::cout << ans << '\n';
}int32_t main() {
#ifdef ORZXKRfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifstd::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);int T = 1;std::cin >> cid >> T;while (T--) dickdreamer();// std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";return 0;
}