|
试题描述
|
|
给定字符串，求它的回文子序列个数。回文子序列反转字符顺序后仍然与原序列相同。
例如字符串aba中，回文子序列为"a", "a", "aa", "b", "aba"，共5个。 注意：内容相同位置不同的子序列算不同的子序列。 |
|
输入
|
|
第一行一个整数T，表示数据组数。
之后是T组数据，每组数据为一行字符串。 |
|
输出
|
|
对于每组数据输出一行，格式为"Case #X: Y"，X代表数据编号（从1开始），Y为答案。答案对100007取模。
|
|
输入示例
|
|
5
aba abcbaddabcba 12111112351121 ccccccc fdadfa |
|
输出示例
|
|
Case #1: 5
Case #2: 277 Case #3: 1333 Case #4: 127 Case #5: 17 |
|
其他说明
|
|
1 ≤ T ≤ 10
字符串长度 ≤ 1000 |
第一眼hash、sa、马拉车什么的就行了。
第二眼样例的答案怎么这么大？
第三眼发现子串可以不连续
第四眼发现N这么小
第五眼发现这是一道裸的DP
第六眼设计出状态f[i][j]表示[i,j]的回文子串数目
第七眼设计出转移
f[i][i]=1
当s[i]!=s[j]时，根据容斥原理f[i][j]=f[i+1][j]+f[i][j-1]-f[i-1][j-1]
当s[i]==s[j]时，答案还要加上f[i-1][j-1]+1即s[i]加入回文串首，s[j]加入回文串尾，即f[i][j]=f[i+1][j]+f[i][j-1]+1
记忆化搜索有些慢（203ms）
#include<cstdio> #include<cctype> #include<queue> #include<cstring> #include<algorithm> #define rep(s,t) for(int i=s;i<=t;i++) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } const int maxn=1010,mod=100007; int f[maxn][maxn]; char s[maxn]; int dp(int l,int r) { int& ans=f[l][r]; if(l>=r) return !(l>r); if(ans) return ans; if(s[l]!=s[r]) return ans=(dp(l+1,r)+dp(l,r-1)-dp(l+1,r-1)+mod)%mod; return ans=(dp(l+1,r)+dp(l,r-1)+1)%mod; } int main() { int T=read(); rep(1,T) { scanf("%s",s+1); int n=strlen(s+1); memset(f,0,sizeof(f)); printf("Case #%d: %d ",i,dp(1,n)); } return 0; }
递推的话要以右端点升序，左端点降序来进行（79ms）
#include<cstdio> #include<cctype> #include<queue> #include<cstring> #include<algorithm> #define rep(s,t) for(int i=s;i<=t;i++) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } const int maxn=1010,mod=100007; int f[maxn][maxn]; char s[maxn]; int main() { int T=read(); rep(1,T) { scanf("%s",s+1); int n=strlen(s+1); for(int j=1;j<=n;j++) { f[j][j]=1; for(int i=j-1;i;i--) if(s[i]==s[j]) f[i][j]=(f[i+1][j]+f[i][j-1]+1)%mod; else f[i][j]=(f[i+1][j]+f[i][j-1]-f[i+1][j-1]+mod)%mod; } printf("Case #%d: %d ",i,f[1][n]); } return 0; }