HDU 1554 Palindromes(回文串+动态规划)

题意：给定若干字符串，输出每个字符串的回文子串个数，这里回文串在原字符串中必须是连续的。

思路：用f(i,j)代表str[i....j]是不是回文串，容易得出递推式f(i,j)=f(i+1,j-1) && str[i]==str[j]，然后将所有的f(i,j)加起来就是答案了。(注意f(i,i)=1和i+1>j-1的情况)

但是这个题目开5000*5000的数组会MLE。于是注意到每次f(i,j)只需要用到f(i+1,j-1)，即它的前两层的状态，所以只要开一个5000*3的滚动数组就可以了。

当然这题还有更好的方法不过我还没想到~

#include<cstdio>
#include<cstring>
#include<iostream>
#define MAXN 5005
using namespace std;
int f[MAXN][3],n,ans;
char s[MAXN];
void getf()
{
n=strlen(s),ans=0;
for(int k=0;k<n;++k)
for(int i=0;i+k<n;++i)
{
  int j=i+k,now=k%3,pre2=(now-2+3)%3;//pre记录的是f(i,j)的上两层，这里的f[i+1][pre2]指的是f(i+1,j-1)
  f[i][now]=(k==0 || (k==1 && s[i]==s[j]) || (i+1<=j-1 && s[i]==s[j] && f[i+1][pre2]));
                  //k==0还有k=1都要特殊处理，防止i+1>j-1

                  ans+=f[i][now];
}
}
int main()
{
while(~scanf("%s",s))
{
getf();
cout<<ans<<endl;
}
}