#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;
}

#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;
}

类似木梳的一道Dp的题目

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
    int num=0,bj=1;
    char x=getchar();
    while(x<'0'||x>'9') {
        if(x=='-')bj=-1;
        x=getchar();
    }
    while(x>='0'&&x<='9') {
        num=num*10+x-'0';
        x=getchar();
    }
    return num*bj;
}
int n,f[2][1000005][2],g[2][1000005],Length[1000005],Left[1000005],Right[1000005],cnt[2],Value[2][1000005],MinRight=0x7fffffff/2,MaxLeft=0;
int Dp() {
    memset(f[1],0x3f,sizeof(f[1]));
    memset(g,0,sizeof(g));
    cnt[1]=0;
    for(int i=1; i<=3; i++)
        for(int j=Length[i]; j<=Length[i]+2; j++)
            if(j>=Length[1])Value[1][++cnt[1]]=j; //确定可选择的值的范围 
    for(int i=1; i<=cnt[1]; i++)f[1][Value[1][i]][0]=Value[1][i]-Length[1]; //更新答案 
    for(int i=2; i<=n; i++) {
        cnt[i%2]=0; //不清空f否则会超时 
        int st=max(1,i-2),ed=min(n,i+2);
        for(int j=st; j<=ed; j++)
            for(int k=Length[j]; k<=Length[j]+2; k++)
                if(k>=Length[i])Value[i%2][++cnt[i%2]]=k;  //确定可选择的值的范围 
        for(int t=1; t<=cnt[i%2]; t++) {
            int j=Value[i%2][t];
            g[i%2][j]=g[i%2][j]=i; //记录当前位置 
            f[i%2][j][0]=f[i%2][j][1]=0x7fffffff/2; //初始值无穷大 
            if(g[((i-1+2)%2)][j]==i-1||i==2) { //必须要上一次被更新过（有值）才能更新 因为没给f初值所以要这么做 
                f[i%2][j][0]=min(f[i%2][j][0],f[(i-1+2)%2][j][0]+j-Length[i]);
                f[i%2][j][1]=min(f[i%2][j][1],f[(i-1+2)%2][j][1]+j-Length[i]);
            }
            for(int s=1; s<=cnt[(i-1+2)%2]; s++) {
                int k=Value[(i-1+2)%2][s];
                if(g[((i-1+2)%2)][k]==i-1||i==2) { //必须要上一次被更新过（有值）才能更新
                    if(k<j)f[i%2][j][1]=min(f[i%2][j][1],f[(i-1+2)%2][k][0]+j-Length[i]);
                    if(k>j)f[i%2][j][0]=min(f[i%2][j][0],f[(i-1+2)%2][k][1]+j-Length[i]);
                }
            }
        }
    }
    int Min=0x7fffffff/2;
    for(int j=1; j<=cnt[n%2]; j++)Min=min(Min,f[n%2][Value[n%2][j]][0]);
    return Min;
}
int main() {
    n=Get_Int();
    for(int i=1; i<=n; i++) {
        Left[i]=Get_Int();
        Right[i]=Get_Int();
        MaxLeft=max(MaxLeft,Left[i]);
        MinRight=min(MinRight,Right[i]);
    }
    for(int i=1; i<=n; i++)Length[i]=MaxLeft-Left[i];
    int ans=Dp();
    for(int i=1; i<=n; i++)Length[i]=Right[i]-MinRight;
    printf("%d\n",ans+Dp());
    return 0;
}

虽然我没有AC但我来抢个沙发