codeforces 1207C

题目链接：https://codeforces.com/problemset/problem/1207/C

直接dp即可

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<stack>
#include<queue>
using namespace std;
typedef long long ll;

const int maxn = 200010;

int T,n;
int x[maxn];
ll a,b,dp[maxn][2]; // 第 i 个路口，0低/1高 
char s[maxn];

ll read(){ ll s=0,f=1; char ch=getchar(); while(ch<'0' || ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0' && ch<='9'){ s=s*10+ch-'0'; ch=getchar(); } return s*f; }

int main(){
	T = read();
	while(T--){
		memset(dp,0x3f,sizeof(dp));
		memset(x,0,sizeof(x));
		n = read(),a = read(), b = read();
		scanf("%s",s+1);
		for(int i=1;i<=n;++i){ x[i] = s[i] - '0'; }
		
		dp[0][0] = b;
		for(int i=1;i<n;++i){
			if(x[i] != 1 && x[i+1] != 1){
				dp[i][0] = min(dp[i-1][0] + a + b, dp[i-1][1] + 2 * a + b); 
				dp[i][1] = min(dp[i-1][0] + 2 * a + 2 * b, dp[i-1][1] + a + 2 * b); 
			}
			else{
				if(x[i]) dp[i][1] = min(dp[i][1],dp[i-1][1] + a + 2 * b);
				else dp[i][1] = min(dp[i-1][0] + 2 * a + 2 * b, dp[i-1][1] + a + 2 * b);
			}
		}
		if(!x[n] && !x[n-1]) dp[n][0] = min(dp[n-1][0] + a + b, dp[n-1][1] + 2 * a + b);
		else dp[n][0] = min(dp[n][0],dp[n-1][1] + 2 * a + b);
		
		printf("%lld
",dp[n][0]);
	}
	
	return 0;
}