Codeforce 835 D. Palindromic characteristics 解析(DP)

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

題目
略，請看原題

前言

想不到這種狀態…

想法

$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=\lfloor\frac{L+R}{2}\rfloor$

程式碼:

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