题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=4632
题目大意: 给你若干个字符串, 回答每个字符串有多少个回文子序列(可以不连续的子串).
解题思路:
设 dp[i][j]为 [i,j] 的回文子序列数, 那么得到状态转移方程:
- dp[i][j]=(dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1]+MOD)%MOD
- if(str[i]==str[j])
dp[i][j]+=dp[i-1][j+1]+1
代码:
- #include<cstdio>
- #include<cmath>
- #include<cctype>
- #include<cstring>
- #include<iostream>
- #include<algorithm>
- #include<vector>
- #include<queue>
- #include<set>
- #include<map>
- #include<stack>
- #include<string>
- #define lc(a) (a<<1)
- #define rc(a) (a<<1|1)
- #define MID(a,b) ((a+b)>>1)
- #define fin(name) freopen(name,"r",stdin)
- #define fout(name) freopen(name,"w",stdout)
- #define clr(arr,val) memset(arr,val,sizeof(arr))
- #define _for(i,start,end) for(int i=start;i<=end;i++)
- #define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
- using namespace std;
- typedef long long LL;
- const int N=1e3+5;
- const int MOD=10007;
- const int INF=0x3f3f3f3f;
- const double eps=1e-10;
- int dp[N][N];
- char str[N];
- int main(){
- int t,cas=0;
- cin>>t;
- while(t--){
- cin>>str;
- int n=strlen(str);
- memset(dp,0,sizeof(dp));
- for(int i=0;i<n;i++){
- dp[i][i]=1;
- }
- for(int len=1;len<n;len++){
- for(int i=0;i+len<n;i++){
- int j=i+len;
- dp[i][j]=(dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1]+MOD)%MOD;
- // 如果 str[i]==str[j], 单独两个字符 str[i],str[j]能组成一个回文串, 同样也能跟 [i-1,j+1] 的所有回文串组成新的回文串
- if(str[i]==str[j])
- dp[i][j]+=dp[i+1][j-1]+1;
- }
- }
- cout<<"Case"<<++cas<<":"<<dp[0][n-1]%MOD<<endl;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2565090.html