Educational Codeforces Round 73 (Rated for Div. 2)D（DP，思维）

#define HAVE_STRUCT_TIMESPEC
#include<bits/stdc++.h>
using namespace std;
long long a[300007],b[300007];
long long dp[300007][5];
long long ans;
int main(){
ios::sync_with_stdio(false);//多组数据输入cin，cout容易超时
cin.tie(NULL);
cout.tie(NULL);
int q;
cin>>q;
while(q--){
int n;
ans=2e18;
cin>>n;
dp[1][0]=0;//第二维表示第一维增加的高度，0即不增加，花费也是0
dp[1][1]=b[1];//增加1高度花费为b[1]
dp[1][2]=2e18;//第一个点最多只需要增加1高度就可以与a[2]不同，所以花费初始化为最大值
for(int i=2;i<=n;++i){//初始化
dp[i][0]=2e18;
dp[i][1]=2e18;
dp[i][2]=2e18;
}
for(int i=1;i<=n;++i)
cin>>a[i]>>b[i];
for(int i=2;i<=n;++i){
for(int j=0;j<3;++j){
for(int k=0;k<3;++k){
if(k+a[i]!=a[i-1]+j){//如果当前a[i]增加k以后的高度和上一位置a[i-1]增加j以后的高度不同，则满足题意
dp[i][k]=min(dp[i-1][j]+b[i]*k,dp[i][k]);//更新位置i增加高度k所需要的最小花费
}
}
}
}
for(int i=0;i<3;++i){
ans=min(dp[n][i],ans);
}
cout<<ans<<"\n";
}
return 0;
}

巴特西

Educational Codeforces Round 73 (Rated for Div. 2)D（DP，思维）

最新文章

热门文章