UVa-11584

先用manacher找到以所有回文串，再暴力统计以每个字符为结尾的所有回文串，然后dp就容易了。最坏情况下是O(n^2) (之后看了一下，这题的时间发现居然是rank 4！）

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<vector>
 6 #define pb push_back
 7 using namespace std;
 8 const int maxn=1010;
 9 char s[maxn];
10 int len;
11 int dp[maxn];
12 vector<int> d[maxn];
13 char ma[maxn*2];
14 int mp[maxn*2];
15 void manacher()
16 {
17     int l=0;
18     ma[l++]='$';
19     ma[l++]='#';
20     for(int i=0;i<len;i++)
21     {
22         ma[l++]=s[i];
23         ma[l++]='#';
24     }
25     ma[l]=0;
26     int mx=0,id=0;
27     for(int i=0;i<l;i++)
28     {
29         mp[i]=mx>i?min(mp[2*id-i],mx-i):1;
30         while(ma[i+mp[i]]==ma[i-mp[i]]) mp[i]++;
31         if(i+mp[i]>mx)
32         {
33             mx=i+mp[i];
34             id=i;
35         }
36     }
37 }
38 void getd()
39 {
40     for(int i=2;i<=(len<<1);i++)
41         for(int j=i;j<i+mp[i];j++)
42             if((j&1)==0) d[j/2-1].pb((2*i-j)/2-1);
43 }
44 int main()
45 {
46     int T;
47     scanf("%d",&T);
48     for(int kase=1;kase<=T;++kase)
49     {
50         memset(mp,0,sizeof(mp));
51         memset(dp,0x3f,sizeof(dp));
52         scanf("%s",s);
53         len=strlen(s);
54         manacher();
55         getd();
56         for(int i=0;i<len;i++)
57         {
58             for(int j=0;j<d[i].size();j++)
59                 dp[i]=min(dp[i],(d[i][j]==0?1:dp[d[i][j]-1]+1));
60             d[i].clear();
61         }
62         printf("%d
",dp[len-1]);
63     }
64 }

然后看到lrj的代码，记忆化搜索，有些暴力。之前听说vis不用每次都初始化，这是第一次见怎么写的。

int kase;
.....
{
    ....
    if(vis[i][j] == kase) return p[i][j];
    vis[i][j] = kase;
    ....
}

int main()
{
    .....
    memset(vis, 0, sizeof(vis));
    for(kase = 1; kase <= T; kase++)
    {
    ....
    }
    .....
}