题解：CF1579G Minimal Coverage

似嫩 · 2021-10-04 11:42:23 · 题解

题意简析

有多组数据

• 给你 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})

总结

想对状态还是。。嗯不难想的 总之也是道神仙题

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("");
    }
}