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

被B题卡了快一个小时才看C题。。满足最优子结构和无后效性就是DP了
这次又是写出了C的时候没写出B呢。。。
设$f_{i,j}$为铺设到$i$位置的时候高度为j的最小花费
那么可以得到转移方程
在$s_i$为1的时候：
$$
\begin{cases}
f[i][0] = INF\
f[i][1] = min(f[i-1][0] + 2a,f[i-1][1] + a) + 2b\
\end{cases}
$$
在$s_i$为0的时候：
$$
\begin{cases}
f[i][0] = min(f[i-1][1] + 2a,f[i-1][0] + a) + b\
f[i][1] = min(f[i-1][0] + 2a,f[i-1][1] + a) + 2b\
\end{cases}
$$
时间复杂度：$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;
}