传送门
题意：
给一个字符串，问其中每一个回文子串的总价值。
回文子串的价值，定义：
1、如果是回文的则价值为1；
2、如果左半个回文部分的价值为k-1，则当前子串的价值为k。
思路：
1、dp[i][j]表示从第i个字符到第j个字符的子串价值，num[i]表示价值为i的子串的个数；
2、先枚举长度1、2的价值，再通过dp[i+1][j-1]尝试更新dp[i][j]的值；
3、由于子串的值可以累加，则还需对num[i]进行处理。
#include <bits/stdc++.h> using namespace std; #define N 5005 int dp[N][N]; char s[N]; int num[N]; int main() { scanf("%s",s); int n = strlen(s); for(int i=0;i<n;i++){ dp[i][i] = 1; } num[1] = n; for(int i=1;i<n;i++){ if(s[i]==s[i-1]) num[2]++,dp[i-1][i] = 2; //在单独枚举长度为2 } for(int i=2;i<n;i++){ for(int j=0;j+i<n;j++){ if(!dp[j+1][j+i-1]) continue; //如果不枚举长度2 则当 i==1 时 dp[j+1][j+1-1] 为 dp[j+1][j] if(s[j]!=s[j+i]) continue; dp[j][j+i] = dp[j][j+(i+1)/2-1] + 1; num[dp[j][j+i]]++; } }j for(int i=n;i>=1;i--){ num[i-1] += num[i]; } for(int i=1;i<=n;i++){ printf(i==1?"%d":" %d",num[i]); } return 0; }
