开发笔记:dpbzoj2436noi2011noi嘉年华

#include
#define fo(i, n) for(int i = 1; i <= (n); i ++)
#define out(x) cerr <<#x <<" = " <n"
using namespace std;
// by piano
template<typename tp> inline void read(tp &x) {
x = 0; char c = getchar(); bool f = 0;
for(; c <&＃39;0&＃39; || c > &＃39;9&＃39;; f |= (c == &＃39;-&＃39;), c = getchar());
for(; c >= &＃39;0&＃39; && c <= &＃39;9&＃39;; x = (x <<3) + (x <<1) + c - &＃39;0&＃39;, c = getchar());
if(f) x = -x;
}
const int N = 1111;
struct NODE {
int l, r, id;
}p[N];
int f[N][N], g[N][N], num[N][N], dp[N][N], pcnt[N][N], ans[N];
int n, x[N], cnt = 0;
inline bool chkmax(int &x, int y) {
return x 1 : 0;
}
inline bool cmp(NODE a, NODE b) {
return (a.l }
#define cal(i, j, x, y) (max(min(x + y + num[i][j], f[i][x] + g[j][y]), min(x + y, f[i][x] + g[j][y] + num[i][j])))
main(void) {
read(n);
for(int i = 1; i <= n; i ++) {
read(p[i].l); read(p[i].r); p[i].r += p[i].l;
x[++ cnt] = p[i].l; x[++ cnt]= p[i].r; p[i].id = i;
}
sort(p + 1, p + n + 1, cmp);
sort(x + 1, x + cnt + 1);
cnt = unique(x + 1, x + cnt + 1) - x - 1;
for(int i = 1; i <= n; i ++) {
p[i].l = lower_bound(x + 1, x + cnt + 1, p[i].l) - x;
p[i].r = lower_bound(x + 1, x + cnt + 1, p[i].r) - x;
++ pcnt[p[i].l][p[i].r];
}
memset(num, 0, sizeof num);
for(int len = 1; len <= cnt; len ++) {
for(int l = 1; l <= cnt; l ++) {
int r = l + len - 1; if(r > cnt) break;
num[l][r] = pcnt[l][r] + num[l + 1][r] + num[l][r - 1] - num[l + 1][r - 1];
}
}
for(int i = 1; i <= cnt; i ++)
for(int j = 1; j <= n; j ++)
f[i][j] = g[i][j] = -6666;
f[0][0] = 0;
for(int i = 1; i <= cnt; i ++) {
for(int j = 0; j <= num[1][i]; j ++) {
chkmax(f[i][j], f[i - 1][j]);
for(int k = 1; k chkmax(f[i][j], f[k][j] + num[k][i]);
if(j - num[k][i] >= 0)
chkmax(f[i][j], f[k][j - num[k][i]]);
}
}
}
for(int j = 0; j <= n; j ++)
chkmax(ans[0], min(j, f[cnt][j]));
g[cnt + 1][0] = 0;
for(int i = cnt; i >= 1; i --) {
for(int j = 0; j <= num[i][cnt]; j ++) {
chkmax(g[i][j], g[i + 1][j]);
for(int k = cnt; k > i; k --) {
chkmax(g[i][j], g[k][j] + num[i][k]);
if(j - num[k][i] >= 0)
chkmax(g[i][j], g[k][j - num[i][k]]);
}
}
}
for(int i = 1; i <= cnt; i ++) {
for(int j = i + 1; j <= cnt; j ++) {
for(int x = 0, y = n; x <= n && y >= 0; x ++) {
while(y) {
int sb = cal(i, j, x, y - 1);
int sn = cal(i, j, x, y);
if(sb >= sn)
-- y;
else break;
}
chkmax(dp[i][j], cal(i, j, x, y));
}
}
}
for(int i = 1; i <= n; i ++)
for(int l = 1; l <= p[i].l; l ++)
for(int r = p[i].r; r <= cnt; r ++) {
chkmax(ans[p[i].id], dp[l][r]);
}
for(int i = 0; i <= n; i ++)
cout <"
";
}