本文共 2094 字，大约阅读时间需要 6 分钟。
看数据量，这题可能是O（n^2）的dp
也可能是区间dp，但是区间dp一般复杂度是O(n^3)，虽然也可以优化，但是比赛的时候那么多人“秒”了，应该不会是那么麻烦的。
套路：设dp[i]表示前i个字符中能拿到的最大贡献。dp[len]就是答案。
如果[L, R]这段区间能组成回文串，那么就有两种决策，删除或则不删除。
删除：dp[R] = dp[L - 1] + a[R - L + 1]
不： dp[R] = dp[R];
取个max就行。
#include #include #include #include #include #include #define IOS ios::sync_with_stdio(false)using namespace std;#define inf (0x3f3f3f3f)typedef long long int LL;#include #include #include #include #include #include #include #include const int maxn = 1e5 + 20;int a[maxn];LL dp[maxn];char str[maxn], sub[maxn];int p[maxn];int manacher(char str[], int lenstr) { str[0] = '*'; //表示一个不可能的值 //目标要插入lenstr+1个'#'，所以长度变成2*lenstr+1 for (int i = lenstr; i >= 0; i--) { //str[lenstr+1]是'\0' //i=lenstr时，i+i+2那个值要赋为'\0'; //总长度只能是lenstr+lenstr+2,所以i从lenstr开始枚举 str[i + i + 2] = str[i + 1]; str[i + i + 1] = '#'; } int id = 0, maxlen = 0; //现在开始在str[2]了 for (int i = 2; i <= 2 * lenstr + 1; i++) { //2*lenstr+1是'#'没用 if (p[id] + id > i) { //没取等号的，只能去到p[id]+id-1 //p[id]+id是越界的，减去i即为区间长度 //p[id]+id-i,这个是所有可能中的最大值了 p[i] = min(p[id] + id - i, p[2 * id - i]); } else p[i] = 1; //记得修改的是p[i] while (str[i + p[i]] == str[i - p[i]]) ++p[i]; if (p[id] + id < p[i] + i) id = i; maxlen = max(maxlen, p[i]); } return maxlen - 1;}bool isok(int be, int en) { int len = en - be + 1; be <<= 1; en <<= 1; int mid = (be + en) >> 1; return p[mid] - 1 >= len;}void work() { int n; cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i]; memset(dp, 0, sizeof dp); cin >> str + 1; int lenstr = strlen(str + 1); strcpy(sub + 1, str + 1); manacher(str, lenstr); for (int i = 1; i <= lenstr; ++i) { for (int j = 1; j <= i; ++j) { if (i - j + 1 > n) continue; if (isok(j, i)) { dp[i] = max(dp[i], dp[j - 1] + a[i - j + 1]); } } } cout << dp[lenstr] << endl;}int main() {#ifdef local freopen("data.txt", "r", stdin);// freopen("data.txt", "w", stdout);#endif int t; cin >> t; while (t--) work(); return 0;}
转载于:https://www.cnblogs.com/liuweimingcprogram/p/6786544.html
