题解 P2703 【[NOI2006]千年虫】

· · 题解

这破玩意肯定过不了审

DP+黑科技优化

首先左右互不干扰，所以我们先处理右边在把左边坐标处理一下（见代码）

跑一样的破玩意就好了

令f[i][j][k]表示处理到i，第i行长为j，最后状态是凹/凸的最小代价

转移：f[i][j][k]=min(f[i-1][j-1][k],f[i-1][p][1-k])(p<j&&s==1 || p>j&&k==0)

然后你把这个东西写出来交上去就TLE身败名裂了

然后我们考虑怎么优化这个东西

令g[i]表示目前这一半i位置上的高度

很容易发现，每次转移的时候，真正有用j的只有一小部分

就g[c]~g[c]+2(i-2<=c<=i+2)这一小段

怎么证明？

当然是靠数学知识证打表找规律啊！

打几个表，大胆猜测这个结论，然后j的枚举范围就是有限的了

然后复杂度就是线性的了，然后就A了

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1000000+10;
const int inf=0x3f3f3f3f;
typedef long long ll;
typedef double ddf;
int n,m;
int l[N],g[N],f[2][N][2],pr,nt;
int t[2],s[2][N];
int ass;
void fuck(){
    memset(f,0x3f,sizeof(f));
    t[1]=0;
    for(int j=1;j<=3;j++){
        for(int k=g[j];k<=g[j]+2;k++){
            if(k>=g[1])s[1][++t[1]]=k;
        }
    }
    for(int i=1;i<=t[1];i++)f[1][i][0]=s[1][i]-g[1];
    pr=0,nt=1;
    for(int i=2;i<=n;i++){
        pr^=1,nt^=1;t[nt]=0;
        int lf=max(1,i-2),rf=min(n,i+2);
        for(int j=lf;j<=rf;j++){
            for(int k=g[j];k<=g[j]+2;k++){
                if(k>=g[i])s[nt][++t[nt]]=k;
            }
        }
        for(int j=1;j<=t[nt];j++){
            f[nt][j][1]=f[nt][j][0]=inf;
            for(int k=1;k<=t[pr];k++){
                if(s[pr][k]>s[nt][j])f[nt][j][0]=min(f[nt][j][0],f[pr][k][1]);
                else if(s[pr][k]<s[nt][j])f[nt][j][1]=min(f[nt][j][1],f[pr][k][0]);
                else f[nt][j][0]=min(f[nt][j][0],f[pr][k][0]),f[nt][j][1]=min(f[nt][j][1],f[pr][k][1]);
            }
            f[nt][j][0]+=s[nt][j]-g[i];
            f[nt][j][1]+=s[nt][j]-g[i];
        }
    }
    int re=inf;
    for(int i=1;i<=t[nt];i++)re=min(re,f[nt][i][0]);
    ass+=re;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d%d",&l[i],&g[i]);
    fuck();
//  cout<<ass<<endl;
    for(int i=1;i<=n;i++)g[i]=N-l[i];
    fuck();
    printf("%d",ass);
    return 0;
}
/*
7
4 4
3 4
3 5
1 3
2 2
2 4
3 3
*/