2020超级码力初赛-Round1-D

2020超级码力初赛-Round1-D

八月 29, 2020

对称前后缀

题意

给定一个字符串 s。 我们令一个字符串的权值为一个字符串的最长对称前后缀长度。

请求出 s 的所有子串的权值的总和。

例如，”abcxyzcba” 的最长对称前后缀的长度为 3，因为 “abc” 和 “cba” 对称。

字符串的长度为 n，1≤n≤3000。 字符串均由小写英文字符组成。

题解

考虑区间dp(L,R) 表示[L,R]区间内 最长的对称前后缀长度

对于长度为1的子串 它的权值为1

对于长度为2的子串 若s[i]==s[i+1]则权值为2 否则为0

对于长度大于3的子串 当s[L]==s[R]

则dp(L,R)由dp(L+1,R-1) 转移得到

若[L+1,R-1]为回文串(即dp(L+1,R-1)==R-L-1)那么加入字符s[L]和s[R] +2权值贡献

否则 +1 权值贡献

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    /**
     * @param s: a string.
     * @return: return the values of all the intervals.
     */
    typedef long long ll;
    ll dp[3004][3004];
    long long suffixQuery(string &s) {
        memset(dp,0,sizeof dp);
        int n=s.size();ll ans=0;
        for(int i=0;i<n;i++)dp[i][i]=1;
        for(int i=0;i<n-1;i++)dp[i][i+1]=(s[i]==s[i+1]?2:0);
        for(int len=3;len<=n;len++){
            for(int L=0;L+len-1<n;L++){
                int R=L+len-1;
                if(s[R]==s[L]){
                    dp[L][R]=dp[L+1][R-1]+(dp[L+1][R-1]==R-L-1?2:1);
                }
            }
        }
        
        for(int R=0;R<n;R++){
            for(int L=0;L<=R;L++){
                ans+=dp[L][R];
            }
        }
        return  ans;
    }
};