Submission #2302466

---

Source Code Expand

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int n, dp[5009], L[5009], L1[5009][5009], L2[5009][5009]; bool I[5009][5009]; string S;

bool ispal(int l, int r) {
	int m = (l + r + 1) / 2;
	int V1 = L1[l][m - 1];
	int V2 = L2[m][r]; if ((r - l) % 2 == 0) V2 = L2[m + 1][r];
	
	if (V1 == V2) return true;
	return false;
}

int main() {
	cin >> n >> S;
	for (int i = 0; i < S.size(); i++) {
		int Z = 0;
		for (int j = i; j < S.size(); j++) {
			Z *= 29;
			Z += (S[j] - 'a' + 1);
			L1[i][j] = Z;
		}
		int ZZ = 0;
		for (int j = i; j >= 0; j--) {
			ZZ *= 29;
			ZZ += (S[j] - 'a' + 1);
			L2[j][i] = ZZ;
		}
	}
	for (int i = 1; i <= n; i++) cin >> L[i];
	for (int i = 1; i <= n; i++) dp[i] = (1LL << 30);
	for (int i = 1; i <= S.size(); i++) {
		for (int j = 0; j < i; j++) {
			if (ispal(j, i - 1) == false) continue;
			dp[i] = min(dp[i], dp[j] + L[i - j]);
		}
	}
	cout << dp[n] << endl;
	return 0;
}

Submission Info

Judge Result