Codeforces1207-C Gas Pipeline

题目大意:在$x$轴的非负区域,有长度为$n$的路,需要在这条路上铺设管道;如果在某个位置是十字路口的话,需要将这个位置的管道高度铺设在$y = 2$的位置上面,而在非十字路口的位置,可以铺设在$y = 1$的位置,也可以铺设在$y = 1$的位置,而不同高度的情况下需要对应高度的管道架;设一单位的管道需要的费用是$a$,一单位管道架需要的费用是$b$,求铺设到终点所需的最小费用

被B题卡了快一个小时才看C题。。满足最优子结构和无后效性就是DP了
这次又是写出了C的时候没写出B呢。。。
设$f_{i,j}$为铺设到$i$位置的时候高度为j的最小花费
那么可以得到转移方程
在$s_i$为1的时候:

在$s_i$为0的时候:

时间复杂度:$O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int T;
ll n,a,b;

char s[2 * maxn];

ll dp[2 * maxn][3];

int main() {
ios::sync_with_stdio(0);
cin>>T;
while(T--) {
dp[0][0] = dp[0][1] = 0;
cin>>n>>a>>b;
cin>>s;
dp[0][1] = INF;
dp[0][0] = b;
for(int i = 1;i <= n;i++) {
if(s[i - 1] == '1') {
dp[i][0] = INF;
dp[i][1] = dp[i - 1][1] + 2 * b + a;
}
else {
dp[i][0] = min(dp[i - 1][0] + a,dp[i - 1][1] + 2 * a) + b;
dp[i][1] = min(dp[i - 1][0] + 2 *a,dp[i - 1][1] + a) + 2 * b;
}
}
cout<<dp[n][0]<<"\n";
}
return 0;
}