C. Gas Pipeline(CF 1207C)(1500)——简单dp

拼搏现实的明天。 2024-04-18 19:12 91阅读 0赞

[题目连接][Link 1]

#include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<set>
    #include<map>
    #include<vector>
    #include<algorithm>
    #define ll long long
    using namespace std;
    const int maxn = 2e5+60;
    char s[maxn];
    ll dp[maxn][3];//dp[][]存的是到该路口为止的花费（不包括该路口右侧的柱子；其中dp[i][1]该路口架设高度为1的状态， [i][2] 架设高度为2的状态 ， 
    const ll inf = 0x3f3f3f3f3f3f;
    
    void init()// 初始化每个状态 为无穷大
    { 
        for(int i = 0; i < maxn; i++)
        { 
            dp[i][1] = dp[i][2] = inf;
        }
    }
    int main()
    { 
        ios_base::sync_with_stdio(false);
        int T;
        cin>>T;
        while(T--)
        { 
            ll n, a, b;
            cin>>n>>a>>b;
            cin>>s;
            init();
            if(s[1] == '0')//第一个路口如何架设取决于他后面的路口是否是十字路口
            { 
                dp[0][1] = a+b;
            }
            else
            { 
                dp[0][2] = a+a+b;
            }
    
            for(int i = 1; i <n; i++)
            { 
                if(s[i] == '1')// 如果该路口是十字路口， 
                { 
                    dp[i][2] = dp[i-1][2]+a+2*b;
                }
                else // 如果是 该路口不是十字路口 分几种情况（可能 这里会有更好的方法）
                { 
                    if(s[i-1] == '1'&& s[i+1] == '1')
                    { 
                        dp[i][2] = dp[i-1][2]+a+2*b;
                    }
                    else if(s[i-1] == '0'&& s[i+1] == '1')
                    { 
                        dp[i][2] = min(dp[i-1][1]+2*a+b, dp[i-1][2]+a+2*b);
                    }
                    else if(s[i-1] == '1')
                    { 
                        dp[i][1] = dp[i-1][2]+2*b+2*a;
                        dp[i][2] = dp[i-1][2]+2*b+a;
                    }
                    else
                    { 
                        dp[i][1] = min(dp[i-1][1]+a+b,dp[i-1][2]+2*a+2*b);
                        dp[i][2] = min(dp[i-1][2]+a+2*b, dp[i-1][1]+2*a+b);
                    }
    
                }
    
    
            }
            cout<<dp[n-1][1]+b<<endl;
    
    
        }
        return 0;
    }

[Link 1]: http://codeforces.com/problemset/problem/1207/