Original link: https://www.shuizilong.com/house/archives/luogu-p1973-noi2011-noi-%E5%98%89%E5%B9%B4%E5%8D%8E/
O(n4) Violence can be written well. . . .
#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]; // one side is j, the other side is at most 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][js[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][js[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;
}
This article is reproduced from: https://www.shuizilong.com/house/archives/luogu-p1973-noi2011-noi-%E5%98%89%E5%B9%B4%E5%8D%8E/
This site is only for collection, and the copyright belongs to the original author.