hdu-4632 Palindrome subsequence (回文子序列计数)
2024-08-25 10:15:07
题目链接: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=;
int dp[][];
int main(){
int n,k;
cin.sync_with_stdio(false);
cin>>n;
int cas=;
while(n--)
{
string s;
cin>>s;
for(int i=;i<s.length();i++)
for(int j=;j<s.length();j++)
dp[i][j]=(i==j);
for(int i=s.length()-;i>=;i--)
{
for(int j=;j<s.length();j++)
{
if(i>=j)
continue;
dp[i][j]=(dp[i+][j]+dp[i][j-]+mod-dp[i+][j-])%mod;
if(s[i]==s[j])
dp[i][j]+=dp[i+][j-]+;
dp[i][j]%=mod;
}
}
cout<<"Case "<<cas++<<": "<<dp[][s.length()-]<<endl;
}
return ;
}
最新文章
- haskell debug
- GDB调试汇编栈堆过程的学习
- 关于那些难改的bug
- 编写linux驱动所用到的头文件(转)
- 【转载】怎么理解Condition
- POI操作Excel常用方法总结
- 深入浅出—JAVA(7)
- 华为软件开发云CloudIDE功能简测
- Shell编程之文本处理
- 使用 Premiere 制作视频简介
- POJ 2368 Buttons
- Web获取客户端物理MAC地址(ocx插件)ActiveX控件
- 你了解ECMAScript吗?
- python的面向对象-实例(对象)的相关知识、实例化
- jQuery Datepicker 插件遇到问题
- MP3 ID3信息编辑器(附源码)
- SQL语言基本操作(聚合函数)
- STS - 配置Tomcat 运行路径
- ES正在弱化type这个概念
- Listener监听器之HttpSessionListener