题解：CF1579G Minimal Coverage

## 题意简析 有多组数据 - 给你 $n$ 条线段，告诉你每条线段的**长度**。 - 你需要把它们放在一条**无限长的数轴**上。 - 放置需满足**当前线段的起点**是**前一个线段的终点**，特别的第一个线段的起点为 $0$。 也就是说，若前一个线段的终点是 $x$,当前长度为 $d$, 那么这个线段必须放在 $[x-d,x]$ 终点变为 $x-d$，或 $[x, x + d]$ 终点变为 $x + d$。 - 请问放置完后所有线段的最小覆盖长度是多少？ - $1\le t\le 10^4, 1\le n\le 10^4$ ## 分析 ~~好耶，居然是DP题~~ 我们把覆盖看成跳跃，一条条跳进行决策显然不现实~~贪心写挂了~~。通过观察可以证明，最后的答案肯定不超过 $2\times l_{\max}$。因为所有的线段都可以在里面左右跳，而不出去（也可参见下面的解释）。 由于数轴是无限长的，从哪里开始没有影响。我们可以规定所有线段在 $[-l_{\max},l_{\max}]$ 之间，如果当前上一个结束位置大于 $0$，就向左跳，否则，就向右跳，这样就不会跳出边界。 解决了如何操作的问题，接下来首先是dp的状态：$dp_{i,l}$ 用来表示当前 $i$ 的结束点到最左边的距离是 $l$ 时，到最右边的距离最小值。于是当前覆盖的长度即为 $l+dp_{i,l}$。最后的答案即为 $\min(l+dp_{n,l})(0\le l\le 2\times l_{\max})$ 然后是转移： - 预处理：$dp_{i,j}=inf,dp_{0,0}=0$ 如果等于 $inf$，说明无法跳到，直接跳出。 - 对于每个线段考虑向左放还是向右放： - 其中 $0\le l\le 2\times l_{\max},0\le i< n$ - 对于 $a_{i+1}$, 如果考虑向左放，那么到左边界的距离变为 $\max(l-a_{i+1},0)$（如果没有超过范围，就减一下，否则它就是现在的最左边），到右边界的距离为 $dp_{i,l}+a_{i+1}$（因为向左跳了那么多）。所以有 $$dp_{i+1,\max(0,l-a_{i+1})} = min(dp_{i+1,\max(0,l-a_{i+1})},dp_{i,l}+a_{i+1})$$ - 如果考虑向右放，那么到右边界的距离变为 $\max(dp_{i,l}-a_{i+1},0)$，到左边界的距离为 $l+a_{i+1}$，所以有 $$dp_{i+1,l+a_{i+1}}=min(dp_{i+1,l+a_{i+1}},\max(dp_{i,l}-a_{i+1},0))$$ 然后我们就愉快地解决了， 复杂度 $O(n\times l_{\max})$ ## 总结 想对状态还是。。嗯不难想的 ~~总之也是道神仙题~~ ```cpp const int INF = 1000000000; int main() { int T = read(); while (T --) { int n = read(); int maxx = 0; for (int i = 0; i < n; i++) { a[i] = read(); maxx = max(maxx, a[i]); } vector<vector<int>> dp(n + 1, vector<int>(2 * maxx + 1, INF)); dp[0][0] = 0; for (int i = 0; i < n; i++) { for (int left = 0; left <= 2 * maxx; left++) { if (dp[i][left] == INF) continue; dp[i + 1][max(left - a[i], 0)] = min(dp[i + 1][max(left - a[i], 0)], dp[i][left] + a[i]); if (left + a[i] < dp[i + 1].size()) { dp[i + 1][left + a[i]] = min(dp[i + 1][left + a[i]], max(dp[i][left] - a[i], 0)); } } } int ans = 2 * maxx + 1; for (int left = 0; left <= 2 * maxx; left++) ans = min(ans, left + dp[n][left]); write(ans), puts(""); } } ```