無從追溯的一道題目。。
題目大意：給出一個字符串 s，要求在 s 中選出3個互不相交的回文子串，求長度之和的最大值
題目分析：考慮 n * n 的 dp，dp[ i ][ k ] 為 s[ 1 : i ] 的前綴中，選出了 j 個回文子串的最大長度，轉移的話也比較簡單，先對字符串建立回文自動機，枚舉以點 i 為結尾的所有回文子串，設枚舉到的節(jié)點為 p：
k == 1：dp[ i ][ 1 ] = len[ p ]k == 2 || k == 3：dp[ i ][ k ] = max( dp[ i ][ k ] , dp[ i - len[ p ]?][ k - 1 ] + len[ p ] )
接下來考慮?Palindrome Series 優(yōu)化，對于上述方程換一種表達方式，設 j 為下標，滿足 s[ j : i ] 為回文子串，那么 dp[ i - len[ p ] ][ k - 1 ] + len[ p ] 就等價于 dp[ j ][ k - 1 ] + i - j，所以我們只需要維護一下 dp[ j ][ k - 1 ] - j 的最大值用于更新即可
代碼；
?
//#pragma GCC optimize(2)
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e6+100;char s[N];int n;LL f[N][4],g[N][4];struct Palindrome_tree
{int nxt[N][26];int fail[N]; // 當前節(jié)點最長回文后綴的節(jié)點int len[N]; // 當前節(jié)點表示的回文串的長度int cnt[N]; // 當前節(jié)點回文串的個數， 在getcnt后可得到全部int sed[N]; // 以當前節(jié)點為后綴的回文串的個數（并不是表示第i結尾的回文串的種類數，如果要求每個點結尾的數的回文串個數，得用last）int record[N]; //record記錄了節(jié)點回文串的結束位置int diff[N],anc[N];char s[N];int tot; // 節(jié)點個數int last; // 上一個節(jié)點int n;//當前字符串的長度 void newnode(){tot++;memset(nxt[tot],0,sizeof(nxt[tot]));cnt[tot]=sed[tot]=len[tot]=fail[tot]=0;}void init(){n=0;tot=-1;newnode();newnode();len[0] = 0, len[1] = -1; // 0為偶數長度根， 1為奇數長度根tot = 1, last = 0;fail[0] = 1;}int getfail(int x, int n){while (s[n - len[x] - 1] != s[n]||n-len[x]-1<0) // 比較x節(jié)點回文串新建兩端是否相等//n-len[x]-1<0這個是我自己加的，多組的時候光第一個條件是不夠的，所以有錯請手動刪除x = fail[x]; // 若不同， 再比較x后綴回文串兩端return x;}void insert(char ch){int c = ch - 'a';//全小寫要用a 全大寫要用A 不然會錯s[++n]=ch;int p = getfail(last, n);// 得到第i個字符可以加到哪個節(jié)點的兩端形成回文串if (!nxt[p][c]){newnode();len[tot] = len[p] + 2; // 在p節(jié)點兩端添加兩個字符fail[tot] = nxt[getfail(fail[p], n)][c]; //tot點的后綴回文，可以由上一個節(jié)點的后綴回文嘗試得到sed[tot] = sed[fail[tot]] + 1; // 以當前節(jié)點為結尾的回文串個數nxt[p][c] = tot; // 新建節(jié)點diff[tot]=len[tot]-len[fail[tot]];anc[tot]=diff[tot]==diff[fail[tot]]?anc[fail[tot]]:fail[tot];}last = nxt[p][c]; // 當前節(jié)點成為上一個節(jié)點cnt[last]++; //當前節(jié)點回文串++record[last] = n;trans(n);}void trans(int i){for(int k=1;k<=3;k++){f[i][k]=f[i-1][k];for(int j=last;j>1;j=anc[j]){g[j][k]=f[i-len[anc[j]]-diff[j]][k]-(i-len[anc[j]]-diff[j]);if(diff[j]==diff[fail[j]])g[j][k]=max(g[j][k],g[fail[j]][k]);if(k==1)f[i][k]=len[j];elsef[i][k]=max(f[i][k],g[j][k-1]+i);}}}void get_cnt(){for (int i = tot; i > 0; i--)cnt[fail[i]] += cnt[i];//fail[i] 的節(jié)點 為 i 節(jié)點的后綴回文串， 所以個數相加}
}tree;int main()
{
#ifndef ONLINE_JUDGE
// freopen("data.in.txt","r",stdin);
// freopen("data.out.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);tree.init();scanf("%s",s+1);n=strlen(s+1);for(int i=1;i<=n;i++)tree.insert(s[i]);printf("%lld\n",f[n][3]);return 0;
}
?
總結
以上是生活随笔為你收集整理的2019ICPC(沈阳) (回文自动机+Palindrome Series优化dp)的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
