• https://www.luogu.com.cn/problem/P1973

O(n4) 暴力写的好是能过得。。。。

#include <lastweapon/io>
using namespace lastweapon;
const int N = 200 + 1, PN = N*2 + 1;
VI P; int L[N], R[N], s[PN][PN];
int pre[PN][N], suf[PN][N]; // 一边为 j，另一边至多
int f[PN][PN];
int n, pn;

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    RD(n); REP(i, n) {
        RD(L[i], R[i]); R[i] += L[i];
        P.PB(L[i]); P.PB(R[i]);
    }
    UNQ(P); REP(i, n) {
        L[i] = LBD(P, L[i]);
        R[i] = LBD(P, R[i]) - 1;
        s[L[i]][R[i]] += 1;
    }

    pn = SZ(P)-1; FOR(len, 1, pn) REP(l, pn-len) {
        int r = l + len;
        s[l][r] += s[l+1][r] + s[l][r-1] - s[l+1][r-1];
    }

    REP(i, pn) pre[i][0] = s[0][i];
    REP(i, pn) suf[i][0] = s[i][pn-1];

    REP(i, pn) REP_1(j, s[0][i]) REP(k, i) checkMax(pre[i][j], max(j <= s[0][k] ? pre[k][j] + s[k+1][i] : 0, j >= s[k+1][i] ? pre[k][j-s[k+1][i]] : 0));
    DWN(i, pn, 0) REP_1(j, s[i][pn-1]) DWN(k, pn, i) checkMax(suf[i][j], max(j <= s[k+1][pn-1] ? s[i][k] + suf[k+1][j] : 0, j >= s[i][k] ? suf[k+1][j-s[i][k]] : 0));

    int z = 0; FOR(i, 0, s[0][pn-1]+1) checkMax(z, min(i, suf[0][i]));
    cout << z << endl;

    REP(i, pn) FOR(j, i, pn) {
        REP(x, s[0][i-1]+1) REP(y, s[j+1][pn-1] +1) {
            checkMax(f[i][j], min(x + s[i][j] + y, pre[i-1][x] + suf[j+1][y]));
        }
    }

    DWN(len, pn-1, 0) REP(l, pn-len) {
        int r = l + len;
        if (l) checkMax(f[l][r], f[l-1][r]);
        if (r != pn-1) checkMax(f[l][r], f[l][r+1]);
    }

    REP(i, n) cout << f[L[i]][R[i]] << endl;
}

Posted by xiaodao
Category: 日常