C. Gas Pipeline (dp)

cf传送门

思路：

设dp[i][0]表示在第i个数字左边的高度为1时的最小值，
dp[i][1]表示在i个数字左边的高度为2时的最小值.
那么我们这一轮已经确定了高度，再结合上一轮的状态，两个高度都知道了，不难得到需要花费的值
这里算出的答案是上个状态的两种情况和当前状态结合之后的最小值,所以不用担心上个状态的最小值和当前状态结合之后不是最小值。
值得注意的是当前数字是0时，如果上一个数字是1那么当前高度一定也只能是1.

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define r0 return 0
#define endl "\n"
#define pii pair<int,int>
#define inf 0x3f3f3f3f
const int N = 2e5 + 5;

const int mod = 998244353;
int g[55][55];
ll dp[N][2];
int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int t;
	cin >> t;
	while (t--)
	{
		memset(dp, 0x3f, sizeof dp);
		int n, a, b;
		cin >> n >> a >> b;
		string s;
		cin >> s;
		dp[0][0] = b;
		for (int i = 1; i < n; i++)
		{
			if (s[i] == '0') // 计算的是当前数字和上一个数字之间的和当前高度
			{
				if (s[i - 1] == '0')
				{
					dp[i][1] = min(dp[i - 1][0] + 2 * a, dp[i - 1][1] + a) + 2 * b;
					dp[i][0] = min(dp[i - 1][0] + a, dp[i - 1][1] + 2 * a) + b;
				}
				else // 如果上一个数字是1那么当前高度只能是1
					dp[i][1] = min(dp[i - 1][0] + 2 * a, dp[i - 1][1] + a) + 2 * b;
			}
			else 
				dp[i][1] = min(dp[i - 1][0] + 2 * a, dp[i - 1][1] + a) + 2 * b;
		}
		dp[n][0] = min(dp[n - 1][1] + 2 * a, dp[n - 1][0] + a) + b; // 最后的别忘了加上
		cout << dp[n][0] << endl;
	}
	r0;
}