CodeForces-1221D Make The Fence Great

传送门：CodeForces-1221D Make The Fence Great

思路分析

因为只和相邻两项比较，所以一个点最多被提升两次
设dp[i][j]表示第i个位置提升j次的答案
那么就可以与dp[i-1][j]来比较转移了

样例输入

3
3
2 4
2 1
3 5
3
2 3
2 10
2 6
4
1 7
3 3
2 6
1000000000 2

样例输出

2
9
0

AC代码

#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <chrono>
#include <random>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) x.size()
#define lowbit(x) x&(-x)
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 0x3f3f3f3f;
const int N=3e5+10;

ll dp[N][3],a[N],b[N];

int main() {
    IOS;
#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    int t;
    cin>>t;
    while(t--) {
        int n;
        cin>>n;
        for(int i=1; i<=n; i++) cin>>a[i]>>b[i];
        dp[1][0]=0;
        dp[1][1]=b[1];
        dp[1][2]=b[1]*2;
        for(int i=2;i<=n;i++){
            dp[i][0]=dp[i][1]=dp[i][2]=2e18;
            for(int j=0;j<=2;j++){
                for(int k=0;k<=2;k++){
                    if(a[i]+k!=a[i-1]+j){
                        dp[i][k]=min(dp[i][k],dp[i-1][j]+k*b[i]);
                    }
                }
            }
        }
        cout<<min(dp[n][0],min(dp[n][1],dp[n][2]))<<endl;


    }




    return 0;
}
&nbsp;