题解 P2314 【[HNOI2005]木梳】

· · 题解

请直接去看p2703题解

直接把输入看成往空白区域上添加方格之后复制p2703代码会炸，至少我的

会炸，这让我十分气愤，以至于我不得不打电话给王八屯子妇女协会把出数

据的下放到苞米地劳改进行大量魔改，但事实上这样十分有效，以至于我隔

壁的大佬直接艹过去了，但他懒得写题解（不屑），所以他就叫我写一个，但我

也懒得写，所以我决定把p2703的题解复制魔改一下就好了（反正思路一样）

令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&&k==1 || p>j&&k==0)

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

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

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

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

就

g[c]-2~g[c](i-2<=c<=i+2)

这一小段

怎么证明？

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

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

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

然后记得开longlong

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1000000+10;
const long long inf=0x7f7f7f7f7f7f7f7f;
typedef long long ll;
typedef double ddf;
typedef int _int;
#define int ll
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,0x7f,sizeof(f));
    t[1]=0;
    for(int j=1;j<=3;j++){
        for(int k=g[j]-2;k<=g[j];k++){
            if(k<=g[1])s[1][++t[1]]=k;
        }
    }
    for(int i=1;i<=t[1];i++)f[1][i][0]=f[1][i][1]=g[1]-s[1][i];
    pr=0,nt=1;
    for(int i=2;i<=n;i++){
        pr^=1,nt^=1;t[nt]=0;
        int lf=max(1ll,i-2),rf=min(n,i+2);
        for(int j=lf;j<=rf;j++){
            for(int k=g[j]-2;k<=g[j];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]+=g[i]-s[nt][j];
            f[nt][j][1]+=g[i]-s[nt][j];
        }
    }
    int re=inf;
    for(int i=1;i<=t[nt];i++)re=min(re,min(f[nt][i][0],f[nt][i][1]));
    ass+=re;
}
_int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&g[i]);
    //fuck();
    fuck();
    printf("%lld",ass);
    return 0;
}