CodeForces 706C - Hard problem
題意:
輸入N(有多少字)、每個字顛倒的成本和每個字，問你不改變這串字的先後順序，藉由顛倒某些字來將這些字排成字典順序最少需要多少成本？
思路:
直接將所有字及所有顛倒後的字存起來，然後紀錄後面的字要滿足比前面的字大的最小成本，逐個更新就是答案。
程式碼:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| #include <string> | |
| #include <cmath> | |
| #include <algorithm> | |
| using namespace std; | |
| const int AMAX = 1e5 + 7; | |
| int N, cost[AMAX]; | |
| long long dp[AMAX][2]; | |
| string s[AMAX][2]; | |
| int main() | |
| { | |
| cin >> N; | |
| for(int i = 1; i <= N; ++i) | |
| { | |
| cin >> cost[i]; | |
| } | |
| for(int i = 1; i <= N; ++i) | |
| { | |
| cin >> s[i][0]; | |
| s[i][1] = s[i][0]; | |
| reverse(s[i][1].begin(), s[i][1].end()); | |
| for(int j = 0; j < 2; ++j) | |
| { | |
| dp[i][j]= 1e18; | |
| for(int k = 0; k < 2; ++k) | |
| { | |
| if(s[i][j] >= s[i - 1][k]) | |
| { | |
| dp[i][j] = min(dp[i][j], dp[i - 1][k] + j * cost[i]); | |
| } | |
| } | |
| } | |
| } | |
| long long ans = min(dp[N][0], dp[N][1]); | |
| cout << (ans == 1e18 ? -1 : ans) << endl; | |
| return 0; | |
| } |