D. Palindromic characteristics 解析(DP)

Codeforce 835 D. Palindromic characteristics 解析(DP)

今天我們來看看CF835D
題目連結

題目
略，請看原題

前言

想不到這種狀態...

@copyright petjelinux 版權所有
觀看更多正版原始文章請至petjelinux的blog

想法

(dp[L][R])代表區間([L,R))是(dp[L][R]-palindrome)
從長度為(2)的區段慢慢算到長度為(n)的區段。
如果(s[L]==s[R-1])，那麼只要([L+1,R-1))是回文，這整段就會是回文，因此(dp[L][R]=dp[L][M]+1)，其中(M=lfloorfrac{L+R}{2} floor)

程式碼:

const int _n=5010;
int t,n,dp[_n][_n],ans[_n],suf[_n];
string s;
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  cin>>s;n=s.length();rep(i,0,n)dp[i][i]=0,dp[i][i+1]=1;
  rep(j,2,n+1)rep(i,0,n+1-j){
    int L=i,R=L+j,m=(L+R)/2;
    if(s[L]==s[R-1] and (dp[L+1][R-1] or L+1==R-1))dp[L][R]=dp[L][m]+1;
  }rep(j,1,n+1)rep(i,0,n+1-j)ans[dp[i][i+j]]++;
  suf[n]=ans[n];per(i,1,n)suf[i]=suf[i+1]+ans[i];
  rep(i,1,n+1)cout<<suf[i]<<' ';
  return 0;
}

標頭、模板請點Submission看
Submission