Codeforce 1221D Make The Fence Great Again （围栏great，找状态dp）

#include <bits/stdc++.h>
using namespace std;
const int maxn=3e5+5;
const long long inf=1e18;
int T, n;
long long dp[maxn][3], cost[maxn], a[maxn];
 
int main(){
    ios::sync_with_stdio(false), cin.tie(0);
    //freopen("in.txt", "r", stdin);
    for(cin>>T; T--; ){
        cin>>n;
        for(int i=1; i<=n; i++) cin>>a[i]>>cost[i];
        for(int i=1; i<=n; i++)
            for(int k=0; k<=2; k++)
                dp[i][k]=inf;
        for(int i=1; i<=n; i++)
            for(int k1=0; k1<=2; k1++)
                for(int k2=0; k2<=2; k2++)
                    if(i==1 || a[i]+k2!=a[i-1]+k1)
                        dp[i][k2]=min(dp[i][k2], dp[i-1][k1]+cost[i]*k2);
        long long ans=min(dp[n][0], min(dp[n][1], dp[n][2]));
        cout<<ans<<"\n";
    }
    return 0;
}