BZOJ 2436: [Noi 2011] Noi 카니발

선인 의 서술 이 준 비 된 느낌 이 든다.총괄 해 볼 까요?DP 선 이산 화 상태 정의 가 교묘 하 다.있다
l[i][j]=max(l[k][j]+c[k][i],l[k][j−c[k][i]])(k∈[0,i−1])
r [i] [j] (구간 [i, Tmax]) 구법 동 리 를 거꾸로 하면 돼.
왜 거꾸로 하 냐 면 두 번 째 질문 을 해 야 되 니까.
우리
강제 선택 i j 구간 의 모든 것 이 작은 사람 이 얼마나 많은 지
g[i][j]=max(l[i][x]+c[i][j]+r[j][y])(x,y∈[0,n])
그리고 사실은 x 가 고정 되 었 을 때 위의 값 은 y 단조 에 관 한 것 이다.그리고 n ^ 3 으로 끝 낼 수 있어 요.
g 배열 이 좌우 로 최대 로 확장 할 수 있다 는 것 을 잊 지 마 세 요.
독자 가 왜 이 안에 단조 성에 대한 증명 이 있 는 지 알 고 싶다 면 잘 그 렸 습 니 다.
http://www.cnblogs.com/Konjakmoyu/p/6602274.html
그렇게 오래 했 는데 56 이면 돼.

#include
#define me(a,x) memset(a,x,sizeof a)
using namespace std;
const int N=201,M=402;
inline int read()
{
    char ch=getchar(); int x=0,f=1;
    while(ch'9'){if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
int s[N],t[N],p[M],g[M][M],c[M][M],l[M][N],r[M][N];
int main()
{
    int n=read(),i,j,x,y,m=0;
    for(i=1;i<=n;i++)
        p[++m]=s[i]=read(),p[++m]=t[i]=s[i]+read();
    sort(p+1,p+1+m);
    m=unique(p+1,p+1+m)-p-1;
    for(i=1;i<=n;i++)
        s[i]=lower_bound(p+1,p+1+m,s[i])-p,
        t[i]=lower_bound(p+1,p+1+m,t[i])-p;
    for(i=0;i<=m;i++)
    {
        for(j=1;j<=n;j++)if(s[j]>=i)c[i][t[j]]++;
        for(j=i+1;j<=m;j++)c[i][j]+=c[i][j-1];
    }
    me(l,-10); me(r,-10); me(g,-10);
    l[1][c[1][1]]=0,l[1][0]=c[1][1];
    for(i=2;i<=m;i++)for(j=0;j<=n;j++)
        for(x=1;x
            l[i][j]=max(l[i][j],max(l[x][j]+c[x][i],l[x][j-c[x][i]]));
    r[m][c[m][m]]=0,r[m][0]=c[m][m];
    for(i=m-1;i>0;i--)for(j=0;j<=n;j++)
        for(x=m;x>i;x--)
            r[i][j]=max(r[i][j],max(r[x][j]+c[i][x],r[x][j-c[i][x]]));
    int ans=0;
    for(i=1;i<=m;i++)for(j=i;j<=m;j++)
    {
        for(y=c[j][m],x=0;x<=c[1][i];x++,y++)
            for(;~y;y--)
            {
                int u=min(x+y,l[i][x]+c[i][j]+r[j][y]);
                if(g[i][j]<=u)g[i][j]=u;
                else break;
            }
        ans=max(ans,g[i][j]);
    }
    for(i=1;i<=m;i++)
        for(j=m;j>=i;j--)g[i][j]=max(g[i][j],g[i][j+1]);
    for(i=1;i<=m;i++)
        for(j=i;j<=m;j++)g[i][j]=max(g[i][j],g[i-1][j]);
    printf("%d
",ans);
    for(i=1;i<=n;i++) printf("%d
",g[s[i]][t[i]]);
    return 0;
}