传送门: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;
}