CodeForces #367 div2 C

题目链接： Hard problem

题意：每个字符串可以选择反转或者不反转，给出反转每个字符串的代价，问使最少的代价使得这个字符串序列成字典序。

dp[i][j] = x ： 第一维是第i个字符串，第二维表示当前字符串是否反转。x表示当前状态下使前i个字符串成字典序的最小代价。

感觉可以做的dp，然后我没写出来。T_T

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <string>
#define maxn 100100
#include <algorithm>
#define inf 1e20
#define LL long long
using namespace std;

LL dp[maxn][2];
LL a[maxn];

string s[maxn];
string ss[maxn];

int main() {
    //freopen("in.cpp", "r", stdin);
    int n;
    while(~scanf("%d", &n)) {
        for (int i=1; i<=n; ++i) {
            scanf("%I64d", &a[i]);
        }
        for (int i=1; i<=n; ++i) {
            cin >> s[i];
            ss[i] = s[i];
            reverse(ss[i].begin(), ss[i].end());
        }

        dp[1][0] = 0;
        dp[1][1] = a[1];

        for (int i=2; i<=n; ++i) {
            dp[i][0] = inf;
            dp[i][1] = inf;
            if (s[i] >= s[i-1]) dp[i][0] = min(dp[i][0], dp[i-1][0]);
            if (s[i] >= ss[i-1]) dp[i][0] = min(dp[i][0], dp[i-1][1]);
            if (ss[i] >= ss[i-1]) dp[i][1] = min(dp[i][1], dp[i-1][1] + a[i]);
            if (ss[i] >= s[i-1]) dp[i][1] = min(dp[i][1], dp[i-1][0] + a[i]);
        }
        LL ans = min(dp[n][0], dp[n][1]);
        if (ans >= inf) ans = -1;
        printf("%I64d
", ans);
    }
    return 0;
}