所有的解空间中,一共存在15中状态,每一种状态满足无后效性的性质,可以用动态规划来维护这15种状态,得到最优解。详细状态可见代码注释
#include <bits/stdc++.h> using namespace std; long long Min(long long a, long long b) { return (a < b ? a : b); } int main() { int n; cin >> n; string s; cin >> s; vector<int> a(n); for (int i = 0; i < n; i++) cin >> a[i]; // dp[0]表示000.. dp[1]表示111.. dp[2]表示222... // dp[3]表示011.. dp[4]表示022.. dp[5]表示100... dp[6]表示122.. dp[7]表示200 dp[8]211 // dp[9]表示012.. dp[10]表示021.. dp[11]表示102... dp[12]表示120.. dp[13]表示201 dp[14]210 vector<vector<long long>> dp(n + 1, vector<long long>(15, 1e13)); dp[0][0] = 0, dp[0][1] = 0, dp[0][2] = 0; for (int i = 1; i <= n; i++) { //变为0 1 2需要的消耗 vector<int> b(3, a[i - 1]); b[s[i - 1] - '0'] = 0; dp[i][0] = dp[i - 1][0] + b[0]; dp[i][1] = dp[i - 1][1] + b[1]; dp[i][2] = dp[i - 1][2] + b[2]; if (i >= 2) { dp[i][3] = Min(dp[i - 1][0], dp[i - 1][3]) + b[1]; dp[i][4] = Min(dp[i - 1][0], dp[i - 1][4]) + b[2]; dp[i][5] = Min(dp[i - 1][1], dp[i - 1][5]) + b[0]; dp[i][6] = Min(dp[i - 1][1], dp[i - 1][6]) + b[2]; dp[i][7] = Min(dp[i - 1][2], dp[i - 1][7]) + b[0]; dp[i][8] = Min(dp[i - 1][2], dp[i - 1][8]) + b[1]; } if (i >= 3) { dp[i][9] = Min(dp[i - 1][3], dp[i - 1][9]) + b[2]; dp[i][10] = Min(dp[i - 1][4], dp[i - 1][10]) + b[1]; dp[i][11] = Min(dp[i - 1][5], dp[i - 1][11]) + b[2]; dp[i][12] = Min(dp[i - 1][6], dp[i - 1][12]) + b[0]; dp[i][13] = Min(dp[i - 1][7], dp[i - 1][13]) + b[1]; dp[i][14] = Min(dp[i - 1][8], dp[i - 1][14]) + b[0]; } } long long ans = 1e13; for (int i = 0; i < 15; i++) { ans = Min(ans, dp[n][i]); } cout << ans << '\n'; }