cf835(预处理 + 记忆化dp)

题目链接: http://codeforces.com/contest/835/problem/D

题意: 定义 k 度回文串为左半部分和右半部分为 k - 1 度的回文串 . 给出一个字符串 s, 问 1 ~ s.size() 度回文串的数目分别为多少 .

思路: 预处理 + 记忆化dp

可以先花 O(n^2) 的时间预处理一下所有字串是否为回文串 . 注意预处理时不能直接枚举 l, r, 不然会出现处理 [l, r] 时 [l + 1, r - 1] 并没有先处理的情况 .不过换个思路, 枚举长度和左端点就好了 .

然后可以直接 dfs 出所有字串的回文度, 因为对于回文串其左右部分是一样的, 所以每次 dfs 一半即可,

这里还可以加个记忆优化, 能将复杂度从 O(n * n * log(n)) 降到 O(n * n).

最后注意一下对于度为 k 的串, 其也是度为 1 ~ k - 1 的串 .

代码:

#include <iostream>
using namespace std;

const int MAXN = 5e3 + 10;
int vis[MAXN][MAXN];//vis[i][j]记录[i,j]是否为回文串
int dp[MAXN][MAXN];//dp[i][j]记录[i,j]的回文度
int sol[MAXN];//sol[i]记录回文度为i的子串数目

int dfs(int l, int r){
    if(l == r) return 1;
    if(!vis[l][r]) return 0;
    if(dp[l][r]) return dp[l][r];
    int len = r - l + 1;
    dp[l][r] += dfs(l, l + len / 2 - 1) + 1;
    return dp[l][r];
}

int main(void){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    string s;
    cin >> s;
    int len = s.size();
    for(int i = 0; i < len; i++){
        vis[i][i] = 1;
        if(i + 1 < len && s[i] == s[i + 1]) vis[i][i + 1] = 1;
    }
    for(int i = 3; i <= len; i++){//i为长度
        for(int j = 0; j + i - 1 < len; j++){//j为左边界
            if(vis[j + 1][j + i - 2] && s[j] == s[j + i - 1]) vis[j][j + i - 1] = 1;
        }
    }
    for(int i = 0; i < len; i++){
        for(int j = i; j < len; j++){
            sol[dfs(i, j)]++;
        }
    }
    for(int i = len - 1; i > 0; i--){
        sol[i] += sol[i + 1];
    }
    for(int i = 1; i <= len; i++){
        cout << sol[i] << " ";
    }
    cout << endl;
    return 0;
}