Codeforces Round #367 (Div. 2) C. Hard problem - dblank

Codeforces Round #367 (Div. 2) C. Hard problem

传送门: C. Hard problem

对于一个字符串,有两种选择,要么翻转要不翻转。而当前状态只与前一个字符串有关,所以在四种状态里面转移。
用dpi表示到第i个字符串不翻转的最小花费,dpi表示第i个字符串翻转的最小花费。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
const double eps = 1e-10, pi = acos(-1.0);
const int inf = 0x3f3f3f3f, N = 100000 + 200, Mod = 110119;
typedef long long  ll;
vector<string> s;
int a[N], l[N];
ll dp[N][2];
int main()
{
    int n;
    while(cin>>n)
    {
        string str;
        memset(dp, 0x3f, sizeof(dp));
        s.clear();
        for(int i = 0; i<n; i++)
            scanf("%d", &a[i]);
        for(int i = 1; i<=n; i++)
        {
            cin>>str;
            s.push_back(str);
        }
        string x, y;
        dp[0][1] = a[0];
        dp[0][0] = 0;
        for(int i = 1; i<s.size(); i++)
        {
            x = s[i-1];
            y = s[i];
            reverse(x.begin(), x.end());
            reverse(y.begin(), y.end());
            if(s[i-1]<=s[i]) dp[i][0] = min(dp[i][0], dp[i-1][0]);
            if(x <= s[i]) dp[i][0] = min(dp[i-1][1], dp[i][0]);
            if(y >= s[i-1]) dp[i][1] = min(dp[i][1], dp[i-1][0] + a[i]);
            if(y >= x) dp[i][1] = min(dp[i-1][1] + a[i], dp[i][1]);
        }
        ll ans = min(dp[n-1][1], dp[n-1][0]);
        if(ans == dp[N-1][1])
            printf("-1\n");
        else printf("%lld\n", ans);
    }
    return 0;
}

相关文章

发表新评论