CF 559E Gerald and Path

题目描述

https://www.codeforces.com/problemset/problem/559/E

简要题意：给定 $n$ 个数轴上的点，以及每个点可以延伸的长度，现在每个点只能向左或者右一个方向延伸，求这 $n$ 个延伸出的线段的并的最大值

$n\le 100$

Solution

首先将所有点按照位置排序，然后我们考虑一个比较简单的 $DP$，我们令 $f[i][j][k]$表示前 $i$ 条线段，最靠右的线段为 $j$，方向为 $k$，然后我们考虑如何转移到第 $i+1$ 条线段，发现这种情况下会算错

这种情况下，我们发现 $j$ 这个线段完全被包含了，也就是说他是没有贡献的

所以我们考虑换一个转移方式，那么我们考虑直接从 $i$ 转移到下一个线段 $j$，然后我们认为 $k\in [i+1,j-1]$ 的线段都没有贡献，注意到这样的答案只会变小，只需要考虑最优答案是否能被计算，然后我们发现这种情况好像算不到

我们的解决方案就是对于 $k\in[i+1,j-1]$ 的线段贪心向右延伸，时间复杂度 $O(n^3)$

#include <iostream>
#include <algorithm>
#define maxn 110
#define INF 1000000000
#define ll long long
using namespace std;

int n;
pair<int, int> a[maxn];

int f[maxn][maxn][2];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i].first >> a[i].second;
    sort(a + 1, a + n + 1); int ans = -INF; a[0].first = -INF;
    fill(f[0][0], f[0][0] + maxn * maxn * 2, -INF); f[0][0][0] = 0; 
    for (int i = 0; i <= n; ++i) 
        for (int j = 0; j <= i; ++j)
            for (int k = 0; k < 2; ++k) {
                if (f[i][j][k] == -INF) continue;
                int Max = -INF, id, dir, rj = a[j].first + a[j].second * k;
                for (int l = i + 1; l <= n; ++l) 
                    for (int o = 0; o < 2; ++o) {
                        int rl = a[l].first + a[l].second * o;
                        if (Max < rl) Max = rl, id = l, dir = o; 
                        f[l][id][dir] = max(f[l][id][dir], f[i][j][k] + Max - rl + min(rl - rj, a[l].second));
                    }
                ans = max(ans, f[i][j][k]);
            }
    cout << ans << "\n";
    return 0;
}