容易想到 $dp$，但是如果直接设 $f[i][j]$ 表示修正完前 $i$ 个位置，第 $i$ 个位置增加了 $j$ 高度显然是不行的
考虑有性质，发现每个位置只会被左右两个位置影响而改变，即如果一边等于它那么才要考虑增加它的位置，并且如果此时另一边恰好比它原本高度大 $1$，这个位置才要再考虑增加高度
所以容易发现，每个位置最多增加 $2$ 的高度，然后就可以直接 $dp$ 了
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=6e5+7; const ll INF=1e18+7; int Q,n,a[N],b[N]; ll f[N][3]; int main() { Q=read(); memset(f,0x3f,sizeof(f)); while(Q--) { for(int i=1;i<=n;i++) f[i][0]=f[i][1]=f[i][2]=INF; n=read(); for(int i=1;i<=n;i++) a[i]=read(),b[i]=read(); f[0][0]=0; f[0][1]=f[0][2]=INF; for(int i=1;i<=n;i++) for(int j=0;j<3;j++) for(int k=0;k<3;k++) if(a[i-1]+k!=a[i]+j) f[i][j]=min(f[i][j],f[i-1][k]+1ll*b[i]*j); ll ans=INF; for(int i=0;i<3;i++) ans=min(ans,f[n][i]); printf("%lld\n",ans); } return 0; }