编程之美回文字符串,DP
发布日期:2021-10-08 15:48:46 浏览次数:5 分类:技术文章

本文共 1385 字,大约阅读时间需要 4 分钟。

时间限制:
2000ms
单点时限:
1000ms
内存限制:
256MB

描述

给定字符串,求它的回文子序列个数。回文子序列反转字符顺序后仍然与原序列相同。例如字符串aba中,回文子序列为"a", "a", "aa", "b", "aba",共5个。内容相同位置不同的子序列算不同的子序列。

输入

第一行一个整数T,表示数据组数。之后是T组数据,每组数据为一行字符串。

输出

对于每组数据输出一行,格式为"Case #X: Y",X代表数据编号(从1开始),Y为答案。答案对100007取模。

数据范围

1 ≤ T ≤ 30

小数据

字符串长度 ≤ 25

大数据

字符串长度 ≤ 1000


样例输入
5abaabcbaddabcba12111112351121cccccccfdadfa
样例输出
Case #1: 5Case #2: 277Case #3: 1333Case #4: 127 Case #5: 17

这题看了好久,始终没思路,最后发现是DP,暂时理解不了,先放着,代码:

#include 
#include
#include
#include
using namespace std;char a[1005];const int INF = 100007;int num[1005];int dp[1005][1005];int main(){ int n; scanf("%d",&n); for(int q = 1; q <= n;q++){ scanf("%s",a); int len = strlen(a); map
ma; for(int i =0;i < len;i++){ if(ma.find(a[i]) == ma.end()){ ma[a[i]] = i; num[i] = ma[a[i]]; } else{ num[i] = ma[a[i]]; ma[a[i]] = i; } } memset(dp,0,sizeof(dp)); for(int d = 0;d < len;d++){ for(int s = 0 ;s < len;s++){ int e = d+s; if(e >= len) break; if(d == 0){ dp[s][e] = 1; } else{ int en = e; while(num[e] >= s && num[e] != e) { dp[s][en] += dp[num[e]+1][en-1] + 1; dp[s][en] %= INF; e = num[e]; } //printf("a %d\n",dp[s][e-1]); dp[s][en] += dp[s][en-1] + 1; // printf("%d\n",dp[s][en]); } } } printf("Case #%d: %d\n",q,dp[0][len-1]); }

转载地址:https://blog.csdn.net/ONE_PIECE_HMH/article/details/45116581 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:武大校赛资格赛 差值维护
下一篇:给定俩个日期求有多少个2.29号

发表评论

最新留言

第一次来,支持一个
[***.219.124.196]2024年03月22日 07时05分04秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

mysql索引篇_MySQL索引篇 2019-04-21
有至少一个用MySQL_Mysql有用的面试题 2019-04-21
mysql select同时update_MySQLSELECT同时UPDATE同一张表 2019-04-21
mysql删除后数据库没变化_mysql之delete删除记录后数据库大小不变 2019-04-21
net mysql start3534_MySQL 5.7.14 net start mysql 服务无法启动-“NET HELPMSG 3534” 的奇怪问题... 2019-04-21
pta两个有序链表的合并_7-1 两个有序链表序列的合并 (20分) --- 内存问题再叙 2019-04-21
python问题描述怎么写_python写文件有时候写不进去怎么办 2019-04-21
qpython3安装lxml_在python的lxml中使用xml目录? 2019-04-21
java 幂取模_快速幂取模算法 2019-04-21
java build path jre_java-如何在安装了jre 7后为Jre 6设置路径? 2019-04-21
java上传下载源码_javaweb简单实现文件上传与下载源代码 2019-04-21
java socket udp 广播_1.Java 的屏幕广播(基于UDP),2.多线程下载器 2019-04-21
java控制热敏打印机的例子.rar_stm32控制热敏打印机 2019-04-21
java clone equals_(原)java中对象复制、==、equals 2019-04-21
java滚动字幕实训报告_Java实习报告 (7000字).doc 2019-04-21
php7 memcached.exe,PHP7 下安装 memcache 和 memcached 扩展 2019-04-21
计算机二级java技巧,计算机二级报java难考吗 2019-04-21
php foreach 数据库,php – 使用foreach将数据库检索的数据排列在HTML表中 2019-04-21
拉格朗日matlab编程例题,Matlab习题讲解.doc 2019-04-21
case是不是php语言关键字,PHP语言 switch 的一个注意点 2019-04-21