首页 > 代码库 > hdu-4632 Palindrome subsequence (回文子序列计数)
hdu-4632 Palindrome subsequence (回文子序列计数)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4632
问题要求回答一串字符串中回文子序列的数量,例如acbca就有 a,c,b,c,a,cc,aa,aca,aca(注意这两个aca的c是不同位置的c,都要累计),aba,cbc,acca,acbca.共13种。
我们如果构造dp[i][j]为区间从i-j的回文子序列个数,当i==j时dp[i][j]=1,当i!=j时,如果字符串i,j位相等,他们便可以从dp[i+1,j-1]转移而来,即dp[i][j]=dp[i+1][j-1]*1+1(这里特地写成*1,因为不是单纯的计数+1,是原先区间[i+1,j-1]的所有回文子序列都可以在左右增加一个当前字符构成新的回文序列,同时还加入单独以两个当前字符构成的回文序列)。这里就计算了以当前字符作为左右临界的回文序列个数,除此之外还需要继承子区间所有的回文序列,这个就与字符i,j是否相等无关了。注意这里不能直接累加dp[i+1][j-1],因为会忽略i+k与j以及i与j-k为左右临界的子序列数。因此dp[i][j]+=dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1](两区间累加,去除重复区间).
#include <iostream> #include <cstdio> #include <vector> #include <map> #include <algorithm> #include <queue> #include <cstring> #define LL long long int using namespace std; const int mod=10007; int dp[1005][1005]; int main(){ int n,k; cin.sync_with_stdio(false); cin>>n; int cas=1; while(n--) { string s; cin>>s; for(int i=0;i<s.length();i++) for(int j=0;j<s.length();j++) dp[i][j]=(i==j); for(int i=s.length()-1;i>=0;i--) { for(int j=0;j<s.length();j++) { if(i>=j) continue; dp[i][j]=(dp[i+1][j]+dp[i][j-1]+mod-dp[i+1][j-1])%mod; if(s[i]==s[j]) dp[i][j]+=dp[i+1][j-1]+1; dp[i][j]%=mod; } } cout<<"Case "<<cas++<<": "<<dp[0][s.length()-1]<<endl; } return 0; }
hdu-4632 Palindrome subsequence (回文子序列计数)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。