鉴于FlashHu大佬讲的这么好（而且我根本不会）我就不再讲一遍了->传送
1 //minamoto 2 #include<iostream> 3 #include<cstdio> 4 #include<algorithm> 5 #define upd(A,L,R) {cmax(A[i][j],A[k][j]+tot[L][R]); 6 if(j>=tot[L][R]) cmax(A[i][j],A[k][j-tot[L][R]]);} 7 #define calc(y) min(x+tot[l][r]+y,Pre[l][x]+suf[r][y]) 8 using namespace std; 9 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 10 char buf[1<<21],*p1=buf,*p2=buf; 11 template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;} 12 template<class T>inline int min(T&a,T&b){return a<b?a:b;} 13 inline int read(){ 14 #define num ch-'0' 15 char ch;bool flag=0;int res; 16 while(!isdigit(ch=getc())) 17 (ch=='-')&&(flag=true); 18 for(res=num;isdigit(ch=getc());res=res*10+num); 19 (flag)&&(res=-res); 20 #undef num 21 return res; 22 } 23 char sr[1<<21],z[20];int C=-1,Z; 24 inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;} 25 inline void print(int x){ 26 if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x; 27 while(z[++Z]=x%10+48,x/=10); 28 while(sr[++C]=z[Z],--Z);sr[++C]=' '; 29 } 30 const int N=205,M=405,inf=0x3f3f3f3f; 31 int s[N],t[N],b[M],tot[M][M],Pre[M][N],suf[M][N],f[M][M]; 32 int main(){ 33 //freopen("testdata.in","r",stdin); 34 int n=read(),m=0,ans; 35 for(int i=1;i<=n;++i){ 36 b[++m]=s[i]=read(); 37 b[++m]=t[i]=read()+s[i]; 38 } 39 sort(b+1,b+1+m); 40 m=unique(b+1,b+1+m)-b-1; 41 for(int i=1;i<=n;++i){ 42 s[i]=lower_bound(b+1,b+1+m,s[i])-b; 43 t[i]=lower_bound(b+1,b+1+m,t[i])-b; 44 for(int l=1;l<=s[i];++l) 45 for(int r=m;r>=t[i];--r) ++tot[l][r]; 46 } 47 for(int i=1;i<=m;++i) for(int j=1;j<=n;++j) 48 Pre[i][j]=suf[i][j]=-inf; 49 for(int i=1;i<=m;++i) 50 for(int j=0;j<=tot[1][i];++j) 51 for(int k=1;k<=i;++k) upd(Pre,k,i); 52 for(int i=m;i;--i) 53 for(int j=0;j<=tot[i][m];++j) 54 for(int k=i;k<=m;++k) upd(suf,i,k); 55 for(int l=1;l<=m;++l) 56 for(int r=l+1;r<=m;++r) 57 for(int y=n,x=0;x<=n;++x){ 58 int p0=calc(y),p1; 59 while(y&&p0<=(p1=calc(y-1))) p0=p1,--y; 60 cmax(f[l][r],p0); 61 } 62 ans=0; 63 for(int j=1;j<=n;++j) cmax(ans,min(Pre[m][j],j)); 64 print(ans); 65 for(int i=1;i<=n;++i){ 66 ans=0; 67 for(int l=1;l<=s[i];++l) 68 for(int r=m;r>=t[i];--r) cmax(ans,f[l][r]); 69 print(ans); 70 } 71 Ot(); 72 return 0; 73 }