A90400.嘉年华 题解

代码见下

#include <bits/stdc++.h>
#define inf (-f[N-1][N-1])
using namespace std;
const int N = 405;

int n, l, r, f[N][N], b[N], tot, cnt[N][N], g[N][N], dp[N][N];
struct tt {
    int l, r;
} a[N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &l, &r),
        b[++tot] = a[i].l = l, b[++tot] = a[i].r = l+r-1;
    sort(b+1, b+tot+1);
    tot = unique(b+1, b+tot+1)-b-1;
    for (int i = 1; i <= n; i++)
        a[i].l = lower_bound(b+1, b+tot, a[i].l)-b,
        a[i].r = lower_bound(b+1, b+tot, a[i].r)-b;
    for (int i = 1; i <= tot; i++)
        for (int j = i; j <= tot; j++)
            for (int k = 1; k <= n; k++)
                cnt[i][j] += (i <= a[k].l && a[k].r <= j);
    memset(f, 192, sizeof(f));
    memset(g, 192, sizeof(g));
    f[0][0] = 0;
    for (int i = 1; i <= tot; i++)
        for (int j = 0; j <= n; j++) {
            f[i][j] = f[i-1][j];
            for (int k = i; k >= 1; k--) {
                f[i][j] = max(f[i][j], f[k-1][j]+cnt[k][i]);
                if (j >= cnt[k][i]) f[i][j] = max(f[i][j], f[k-1][j-cnt[k][i]]);
            }
        }
    g[tot+1][0] = 0;
    for (int i = tot; i >= 1; i--)
        for (int j = 0; j <= n; j++) {
            g[i][j] = g[i+1][j];
            for (int k = i; k <= tot; k++) {
                g[i][j] = max(g[i][j], g[k+1][j]+cnt[i][k]);
                if (j >= cnt[i][k]) g[i][j] = max(g[i][j], g[k+1][j-cnt[i][k]]);
            }
        }
    int ans = -inf;
    for (int j = 0; j <= n; j++)
        ans = max(ans, min(j, f[tot][j]));
    printf("%d\n", ans);
    for (int i = 1; i <= tot; i++)
        for (int j = i; j <= tot; j++) {
            int l = cnt[1][i-1];
            for (int r = 0; r <= cnt[j+1][tot]; r++) {
                while (l && max(min(f[i-1][l]+g[j+1][r]+cnt[i][j], l+r), min(f[i-1][l]+g[j+1][r], l+r+cnt[i][j]))
                <= max(min(f[i-1][l-1]+g[j+1][r]+cnt[i][j], l-1+r), min(f[i-1][l-1]+g[j+1][r], l-1+r+cnt[i][j]))) --l;
                dp[i][j] = max(dp[i][j], max(min(f[i-1][l]+g[j+1][r]+cnt[i][j], l+r), min(f[i-1][l]+g[j+1][r], l+r+cnt[i][j]))); 
            }
        }
    for (int i = 1; i <= n; i++) {
        int ans = 0;
        for (int l = 1; l <= a[i].l; l++)
            for (int r = a[i].r; r <= tot; r++)
                ans = max(ans, dp[l][r]);
        printf("%d\n", ans);
    }
    return 0;
}