暑假补题记3

Problem - C - Codeforces

思路：一道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;
}