再次回文
输入:标准输入
输出:标准输出
时间限制: 2秒
是àpalindorme的读取相同的从左边,因为它从右侧的一个或多个字符的序列。例如,Ž,TOT和女士的 回文,但是,ADAM是不是。
给定一个序列S Ñ资本拉丁字母。有多少种方法可以有符号数(可能为0)的比分淘汰,其余的序列成为一个palidrome的。 应认为是相同的,唯一不同的顺序得分Varints 。
输入
输入文件包含多个测试案例(小于15)。第一行包含一个整数Ţ 表示多少测试用例都遵循。
每个ŧ线包含的序列S(1≤N≤60) 。因此,实际上各条生产线是一个测试案例。
产量
对于每个测试案例输出一行一个整数 - 号的方法。
样例输入 样例输出
3 BAOBAB AAAA ABA |
22 15 5 |
题意:给定一个字符串,求出字符串中是回文的子字符串。
思路:dp,跟删除字符形成回文有点像。
如果 str[i] == str[j] 那么 dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1] + dp[i + 1][j - 1] + 1 = dp[i + 1][j] + dp[i][j - 1] + 1
如果不相等, 那么dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]
代码:
#include <stdio.h>
#include <string.h> int t, n, vis[70][70];
long long d[70][70];
char sb[65]; long long dp(int i, int j) {
long long ans = d[i][j];
if (vis[i][j]) return ans;
vis[i][j] = 1;
if (i > j)
ans = 0;
else if (i == j)
ans = 1;
else if (sb[i] == sb[j]) {
ans = dp(i + 1, j) + dp(i, j - 1) + 1;
}
else {
ans = dp(i + 1, j) + dp(i, j - 1) - dp(i + 1, j - 1);
}
if (ans > d[i][j]) {
d[i][j] = ans;
}
return ans;
}
int main() {
scanf("%d%*c", &t);
while (t --) {
gets(sb);
n = strlen(sb);
memset(vis, 0, sizeof(vis));
memset(d, 0, sizeof(d));
printf("%lld\n", dp(0, n - 1));
}
return 0;
}
uva10617 - Again Palindrome(dp)的更多相关文章
-
uva 10453 - Make Palindrome(dp)
题目链接:10453 - Make Palindrome 题目大意:给出一个字符串,通过插入字符使得原字符串变成一个回文串,要求插入的字符个数最小,并且输出最后生成的回文串. 解题思路:和uva 10 ...
-
UVA 10739 String to Palindrome(dp)
Problem H String to Palindrome Input: Standard Input Output: Standard Output Time Limit: 1 Second In ...
-
POJ 3280 Cheapest Palindrome DP题解
看到Palindrome的题目.首先想到的应该是中心问题,然后从中心出发,思考怎样解决. DP问题通常是从更加小的问题转化到更加大的问题.然后是从地往上 bottom up地计算答案的. 能得出状态转 ...
-
CF 335B. Palindrome(DP)
题目链接 挺好玩的一个题,1Y... #include <cstdio> #include <cstring> #include <iostream> using ...
-
POJ 3280 Cheapest Palindrome(DP)
题目链接 被以前的题目惯性思维了,此题dp[i][j],代表i到j这一段变成回文的最小花费.我觉得挺难的理解的. #include <cstdio> #include <cstrin ...
-
uva 10453 - Make Palindrome(dp, 记录路径)
题目 题意: 给一个字符串 ,判断最少插入多少个字符 使字符串成为回文串, 并输出回文串. 思路:先用dp判断需要个数, 再递归输出路径. #include <iostream> #inc ...
-
hdu 1513 &;&; 1159 poj Palindrome (dp, 滚动数组, LCS)
题目 以前做过的一道题, 今天又加了一种方法 整理了一下..... 题意:给出一个字符串,问要将这个字符串变成回文串要添加最少几个字符. 方法一: 将该字符串与其反转求一次LCS,然后所求就是n减去 ...
-
POJ1159 Palindrome(dp)
题目链接. 分析: 感叹算法的力量. 方法一: 设 dp[i][j] 为字符串 s, 从 i 到 j 需要添加的最少字符数. 那么如果 s[i] == s[j], dp[i][j] = dp[i+1] ...
-
poj 3280 Cheapest Palindrome ---(DP 回文串)
题目链接:http://poj.org/problem?id=3280 思路: dp[i][j] :=第i个字符到第j个字符之间形成回文串的最小费用. dp[i][j]=min(dp[i+1][j]+ ...
随机推荐
-
前端开发---ppt展示页面评论区展示
1. 工程地址:https://github.com/digitalClass/web_page 网站发布地址: http://115.28.30.25:8029/ 2. 由于后端同学希望按照 sta ...
-
记 Mac Pro 系统升级后,编译安装 PHP-5.6.28 / PHP-7.0 报错修复过程
买 Mac Pro 的时候,系统为 OS X 10.11.5,编译 PHP-5.6.21 的时候,也遇到一些坑,安装过程记录如下: Mac Pro 编译安装 PHP 5.6.21 及 问题汇总 后来, ...
-
http://five-js.envylabs.com/
一个很有意思的播报javascript最新资讯的网站http://five-js.envylabs.com/
-
js 正则表达式中的惰性匹配
今天看到了一个正则的问题,在其实使用了如下的符号: var reg = /\{(.+?)\}/g; 其中的?号让我疑惑了很久,其实他在这里是惰性匹配的意思,就是能匹配的尽量少匹配.相反,如果不加这个? ...
-
手写事件代理函数 (Delegated function)
‘手写 ’ 这个词 ,面试是不是听过无数遍呢 ! 今天我们来手写一个这样的事件委托函数 => function( parent, selector, type , handle) {} 你需 ...
-
Git操作中crlf和lf冲突问题
多人参与项目开发的时候,经常会遇到代码格式化不一致,在提交的时候出现很多冲突的情况.其中换行符冲突就是一种,在不同的系统平台上是不一样的.UNIX/Linux 使用的是 0x0A(LF),早期的 Ma ...
-
章节九、5-IE Driver
一.下载IE浏览器驱动,然后解压到存放谷歌和火狐驱动的相同路径中(请观看前面的章节) 下载地址一:http://selenium-release.storage.googleapis.com/inde ...
-
普通路由器刷开源固件DD-WRT的简单过程
DD-WRT是基于Linux的无线路由软件,功能强大,它提供了许多一般路由器的软体所没有的功能,将路由器固件升级到DD-WRT可以提升内建于预设固件的限制,并将其转换成强大且具有进阶功能的商业级路由器 ...
-
判断单向连通图(拓扑排序+tarjan缩点)
题意: 给你一个有向图,如果对于图中的任意一对点u和v都有一条从u到v的路或从v到u的路,那么就输出’Yes’,否则输出’No’. 理解:当出现两个及以上入度为0的点(有一个就可能是别人到它,有两个的 ...
-
JavaScript(JS)基本语法(一)
https://www.cnblogs.com/haiyan123/p/7577598.html 一.JavaScript的历史 1992年Nombas开发出C-minus-minus(C--)的嵌入 ...