题解：CF1221D Make The Fence Great Again

DP

定义

dp_{i,0/1/2}

分别表示

a_i

增加

0/1/2

的长度且满足条件的最小花费。

因为每个

a_i

每次上升的长度不超过

2

，这点容易证明，这里不详细说了。

转移

\sum_{i=1}^n \sum_{j=0}^2 dp_{i,j} = \sum_{k=0}^2 dp_{i-1,k} (a_i + j \ne a_{i-1} + k)

答案

ans = \min(dp_{n,0},dp_{n,1},dp_{n,2})

代码

CPP

#include<bits/stdc++.h>
#define int long long
#pragma GCC optimize(3)
using namespace std;
const int maxn = 300010;
const int inf = 1e18;
const int hs = 131;// 或 1331
//unsigned long long 
//cout << fixed << setprecision(3)
//cout << setw(5) << 
//continue
int a[maxn], b[maxn], dp[maxn][3];
signed main(){
    freopen("fence.in", "r", stdin);
    freopen("fence.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while(t--){
    	int n;
    	cin >> n;
    	for(int i = 1;i <= n;i++) cin >> a[i] >> b[i];
    	for(int i = 1;i <= n;i++){
    		dp[i][0] = dp[i][1] = dp[i][2] = inf;
    		for(int j = 0;j < 3;j++){
    			for(int k = 0;k < 3;k++){
    				if(a[i - 1] + k != a[i] + j) dp[i][j] = min(dp[i][j], dp[i - 1][k] + b[i] * j);
    			}
    		}
    	}
    	cout << min({dp[n][0], dp[n][1], dp[n][2]}) << endl;
    }
    return 0;
}

感谢阅读！

题解：CF1221D Make The Fence Great Again

文章操作

DP

定义

转移

答案

代码

相关推荐

评论

题解：CF1221D Make The Fence Great Again