CodeForces #367(706C)|动态规划

706C - Hard Problem

题目大意

有一列字符串，你可以翻转一些字符串使得这一列字符串按字典序排列（翻转操作代价 ci ）。问最小代价。

题解

很多dp题喜欢披着字符串的羊皮啊。。

要注意到的是相等也是满足字典序的QwQ。

注意到字典序排列满足无后效性，故考虑DP。

令 dp[i][0] 表示不翻转第i个字符串时1~i按字典序排列的最小代价， dp[i][1] 表示翻转第i个字符串时xxxx。

dp[i][0]=min{dp[i−1][0]dp[i−1][1]str[i−1]<str[i]rev(str[i−1])<str[i]}

dp[i][1]=min{dp[i−1][0]+c[i]dp[i−1][1]+c[i]str[i−1]<rev(str[i])rev(str[i−1])<rev(str[i])}

dp[i][0]=0;dp[i][1]=c[i]

注意到如果全开数组会爆内存。。只能vector套string了。。。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
typedef long long ll;
const ll inf = 0x7f7f7f7f7f7f7f7fll;
const int N = 200005;
#define rep(i,j,k) for(i=j;i<k;++i)
using namespace std;

vector<string> str, str_rev;
ll c[N], dp[N][2];

int main() {
    int n, i;
    string s;
    cin >> n;
    rep(i,0,n) cin >> c[i];
    rep(i,0,n) {
        cin >> s;
        str.push_back(s);
        reverse(s.begin(), s.end());
        str_rev.push_back(s);
    }
    memset(dp, 0x7f, sizeof dp);
    dp[0][0] = 0;
    dp[0][1] = c[0];
    rep(i,1,n) {
        if (str    [i - 1] <= str    [i]) dp[i][0] = min(dp[i - 1][0]       , dp[i][0]);
        if (str_rev[i - 1] <= str    [i]) dp[i][0] = min(dp[i - 1][1]       , dp[i][0]);
        if (str    [i - 1] <= str_rev[i]) dp[i][1] = min(dp[i - 1][0] + c[i], dp[i][1]);
        if (str_rev[i - 1] <= str_rev[i]) dp[i][1] = min(dp[i - 1][1] + c[i], dp[i][1]);
    }
    if (dp[n - 1][0] == inf && dp[n - 1][1] == inf)
        cout << -1;
    else
        cout << min(dp[n - 1][0], dp[n - 1][1]);
    return 0;
}