---
title: Codeforce 835 D. Palindromic characteristics 解析(DP)
description: "Codeforce 835 D. Palindromic characteristics 解析(DP)"
disqus: hackmd
---
<meta name="robots" content="Codeforce 835 D. Palindromic characteristics 解析(DP)">
<!-- toc -->

# Codeforce 835 D. Palindromic characteristics 解析(DP)
今天我們來看看CF835D
[題目連結](https://codeforces.com/problemset/problem/835/D)

> **題目**
略，請看原題

### 前言
想不到這種狀態...

<div class="VVVcopyrightAAA";>@copyright petjelinux 版權所有<br>
<a href="https://www.cnblogs.com/petjelinux/">觀看更多正版原始文章請至petjelinux的blog</a></div>

### 想法
$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](https://codeforces.com/contest/835/submission/91953767)