Codeforces Round 73 D dp

痛定思痛。 2024-04-20 08:36 144阅读 0赞

链接：http://codeforces.com/contest/1221/problem/D

题意：有一排栅栏，每个栅栏有一个高度和升高一单位所需money，求让相邻两个栅栏高度互不相同的最小花费。

题解：每个栅栏被修改只有三种情况，分别是修改0，修改1，修改2 。然后，背包。

代码：

#include<bits/stdc++.h>
using namespace std;
const int M=3e5+50;
#define ll long long
ll n,m,a[M],b[M],dp[M][3];
int main(){
    int T;scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%lld%lld",&a[i],&b[i]);
        dp[1][0]=0;
        dp[1][1]=b[1];
        dp[1][2]=b[1]+b[1];
        for(int i=2;i<=n;i++){
            for(int j=0;j<=2;j++){
                dp[i][j]=1e18;
                for(int k=0;k<=2;k++){
                    if(a[i]+j!=a[i-1]+k){
                        dp[i][j]=min(dp[i][j],dp[i-1][k]+b[i]*j);
                    }
                }
            }
        }
        printf("%lld\n",min(dp[n][0],min(dp[n][1],dp[n][2])));
    }
    return 0;
}