Educational Codeforces Round 73 D. Make The Fence Great Again

Problem - D - Codeforces

概要

長さnの数列a, bが与えられる。aの各要素は好きな回数+1してよく、a[i]を+1するごとにコストがb[i]かかる。
a[i]の隣接する各2項が等しくならないように上記操作を行うとき、コストの最小値を求めよ。

制約

1 ≦ n ≦ 3 * 10^5
1 ≦ a[i], b[i] ≦ 10^9

方針

重要な考察として、最適な操作において各項が+1される回数は、各項ごとに2回以内である。(要証明)

よって、各a[i]を2回以内+1する全ての場合を考えるような、次のDPで解くことができる。
dp[i][j] = i番目までを考え、かつi番目のa[i]に+1がj回されているときにかかるコストの最小値。

解答

Submission #60962169 - Codeforces

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int q;
	cin >> q;
 
	rep(_, q){
 
		int n;
		cin >> n;
 
		ll a[n];
		ll b[n];
		rep(i, n) cin >> a[i] >> b[i];
 
		ll INF = 1LL << 62;
		vector<vector<ll>> dp(n, vector<ll>(3, INF));
 
		dp[0][0] = 0;
		dp[0][1] = b[0];
		dp[0][2] = 2 * b[0];
 
		rep(i, n-1){
			for(int x = 0; x < 3; x++){
				for(int y = 0; y < 3; y++){
					if(a[i+1] + x != a[i] + y){
						// cout << i << "," << x << "," << y << "," <<  dp[i+1][x] << "," << dp[i][y] + x * b[i+1] << endl;
						dp[i+1][x] = min(dp[i+1][x], dp[i][y] + x * b[i+1]);
					}
				}
			}
		}
 
		cout << min({dp[n-1][0], dp[n-1][1], dp[n-1][2]}) << endl;
	}
 
}