首页 > 代码库 > scut 125. 笔芯回文
scut 125. 笔芯回文
https://scut.online/p/125
看数据量,这题可能是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 <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> #include <bitset> 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; }
scut 125. 笔芯回文
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。