CF-706C Hard problem 题解

题目大意

给你n个字符串，每个字符串可以反转，反转需要$c_i$的花费，求使这n个字符串呈升序所花费的最小花费。

解题思路

刚开始没想到是dp。

后面想到了倒是很简单写完了。

发现wa在了61。。

后面卡了好久，去cf看了看样例。

发现有个判断没判断到。

吐了。。

发现还是自己的思维不够全面。

因为有可能前面那一项需要反转，但是你只能比前一项不反转大，这个时候是不行的。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <list>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int N = 1e5 + 5;
const ll INF = 1e18;
string s[N], f[N];
ll cost[N];
ll dp[N][2];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n; cin >> n;
	for (int i = 1; i <= n; i++)	cin >> cost[i];
	for (int i = 1; i <= n; i++) {
		cin >> s[i];
		dp[i][1] = dp[i][0] = INF;
		for (int j = s[i].length() - 1; j >= 0; j--)	f[i] += s[i][j];
	}
	dp[1][0] = 0; dp[1][1] = cost[1];
	int flag = 1;
	for (int i = 2; i <= n; i++) {
		if (max(s[i], f[i]) < min(s[i - 1], f[i - 1])) {//就是这个判断
			flag = 0; break;
		}
		if (s[i] >= s[i - 1])	dp[i][0] = min(dp[i][0], dp[i - 1][0]);
		if (s[i] >= f[i - 1])	dp[i][0] = min(dp[i][0], dp[i - 1][1]);
		if (f[i] >= s[i - 1])	dp[i][1] = min(dp[i][1], dp[i - 1][0] + cost[i]);
		if (f[i] >= f[i - 1])	dp[i][1] = min(dp[i][1], dp[i - 1][1] + cost[i]);
	}
	if (min(dp[n][0], dp[n][1]) != INF)	cout << min(dp[n][0], dp[n][1]) << endl;
	else cout << -1 << endl;
}