题解：CF1221D Make The Fence Great Again
wqc2011
·
·
题解
传送门（洛谷）
传送门（CF）
DP
定义
因为每个 $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;
}
```
感谢阅读！