C

有点郁闷，DP我怎么一个小时才写出来。

题意：给一个长度为n的01串，要通一座桥好像，1表示这个桥必须二层，也就是柱子得2根，0表示一层，二层都可以，给了桥面的花费a,柱子的花费b，求最小花费

思路:f[i][j]，第i个位置，并且桥目前层数为j+1的最小花费，转移就好了。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=2e5+10;
const ll INF=1e17;

ll f[maxn][2];
char s[maxn];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,a,b;
        scanf("%d%d%d",&n,&a,&b);
        scanf("%s",s+1);
        f[0][0]=0;
        f[0][1]=INF;
        for(int i=1; i<=n-1; i++)
        {
            f[i][0]=f[i][1]=INF;
            if(s[i]==‘0‘)
            {
                if(s[i+1]==‘0‘)
                {
                    if(f[i-1][0]!=INF) f[i][0]=f[i-1][0]+a+b;
                    if(f[i-1][1]!=INF)
                    {
                        f[i][1]=f[i-1][1]+a+2*b;
                        f[i][0]=min(f[i][0],f[i-1][1]+2*a+b);
                    }
                }
                else
                {
                    if(f[i-1][1]!=INF) f[i][1]=f[i-1][1]+a+2*b;
                    if(f[i-1][0]!=INF) f[i][1]=min(f[i][1],f[i-1][0]+2*a+2*b);
                }
            }
            else
            {
                if(f[i-1][1]!=INF) f[i][1]=f[i-1][1]+a+2*b;
            }
//            printf("%lld %lld %lld\n",i,f[i][0],f[i][1]);
        }
        printf("%lld\n",min(f[n-1][0]+a+b,f[n-1][1]+2*a+b)+b);
    }
}

View Code

 

D

 

E