思路：一道dp，首先明确vis含义，vis[i-1][0]代表的是上一步是一个1的柱子地最优解，vis[i-1][1]代表的是上一个是一个2的柱子的最优解，然后就初始状态第一个题目是一定是0开始所以vis[0][1]="非常大的数" vis[0][0]=a+b,就是一个1的柱子加一个1的管道，然后开始遍历每一个节点，当他是一个路口的时候，就必须是要来到1所以 方程是vis[i][0]=inf,vis[i][1]=min(vis[i-1][0]+a*2+b*2,vis[i-1][1]+a+b*2);
前面那个就是不能在向0走，后面那个就是向1走，前一步在1柱子的时候向2走和前一个在2柱子的时候在向2走，然后求最小，
再下来就是不是路口的时候，可以向2也可以向1走求最小就可以。
然后结果就是因为最后一个一定是0所以是vis[n-1][0]+b;最后一根柱子n-1就是在最后一个到0的最优解
#include <bits/stdc++.h> #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <cmath> #define int long long #define inf 884888488848997 using namespace std; const int N=2e5+8; vector< pair<int,int> > q; int vis[N][2]; int32_t main() { ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t; cin>>t; while (t--) { int n, a, b; cin >> n >> a >> b; string s; cin >> s; ::memset(vis,0,sizeof (vis)); vis[0][1] = inf, vis[0][0] = a + b; for(int i=1;i<s.size();i++) { int k=s[i]-'0'; if(k) { vis[i][0]=inf; vis[i][1]=min(vis[i-1][0]+2*a+2*b,vis[i-1][1]+a+2*b); } else { vis[i][0]=min(vis[i-1][0]+a+b,vis[i-1][1]+2*a+b*2); vis[i][1]=min(vis[i-1][0]+2*a+b,vis[i-1][1]+a+2*b); } } cout<<vis[n-1][0]+b<<endl; } return 0; }