hdu 1513

时间:2021-11-21 21:28:41

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1513

思路:正反分别求一次LCS,利用滚动数组对二取余滚动

 #include<stdio.h>
#include<string.h>
#include<iostream>
#include<math.h>
using namespace std; char s1[],s2[];
int dp[][],n; void lcs()
{
int i,j;
memset(dp,,sizeof(dp));
for(i=;i<=n;i++)
{
for(j=;j<=n;j++)
{
int x=i%;
int y=-x;
if(s1[i-] == s2[j-])
dp[x][j]=dp[y][j-]+;
else
dp[x][j]=max(dp[y][j],dp[x][j-]);
}
}
} int main()
{
int i,j;
while(~scanf("%d",&n))
{
scanf("%s",s1);
for(i=;i<n;i++)
{
s2[i]=s1[n--i];
}
s2[i]='\0';
lcs();
printf("%d\n",n-dp[n%][n]);
}
return ;
}

hdu 1513的更多相关文章

  1. HDU 1513 Palindrome(最长公共子序列)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1513 解题报告:给定一个长度为n的字符串,在这个字符串中插入最少的字符使得这个字符串成为回文串,求这个 ...

  2. HDU 1513 Palindrome:LCS(最长公共子序列)or 记忆化搜索

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1513 题意: 给你一个字符串s,你可以在s中的任意位置添加任意字符,问你将s变成一个回文串最少需要添加 ...

  3. hdu 1513&lpar;dp&plus;滚动数组&rpar;

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1513 思路:n这么大,可以采用滚动数组,然后就是求原串和反串的LCS了. #include<io ...

  4. hdu 1513 Palindrome【LCS滚动数组】

    链接: http://acm.hdu.edu.cn/showproblem.php?pid=1513 http://acm.hust.edu.cn/vjudge/contest/view.action ...

  5. hdu 1513 &amp&semi;&amp&semi; 1159 poj Palindrome &lpar;dp&comma; 滚动数组, LCS&rpar;

    题目 以前做过的一道题, 今天又加了一种方法 整理了一下..... 题意:给出一个字符串,问要将这个字符串变成回文串要添加最少几个字符. 方法一: 将该字符串与其反转求一次LCS,然后所求就是n减去 ...

  6. hdu 1513&lpar;滚动数组&rpar;

    Palindrome Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total ...

  7. HDU 1513 最长子序列

    Palindrome Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total ...

  8. HDU 1513 Palindrome

    题目就是给一个字符串问最少插入多少个字符能让原字符串变为回文字符串. 算法: 用原串的长度减去原串与翻转后的串的最大公共字串的长度,就是所求答案. //#define LOCAL #include & ...

  9. HDU 1513 &amp&semi;&amp&semi; POJ 1159 Palindrome &lpar;DP&plus;LCS&plus;滚动数组&rpar;

    题意:给定一个字符串,让你把它变成回文串,求添加最少的字符数. 析:动态规划是很明显的,就是没有了现思路,还是问的别人才知道,哦,原来要么写,既然是回文串, 那么最后正反都得是一样的,所以我们就正反求 ...

随机推荐

  1. windows下php连接sqlserver2008

    如果你需要和sql server通信需要到http://msdn.microsoft.com/en-us/sqlserver/ff657782.aspx自行下载微软提供的The SQL Server ...

  2. vbox下Oracle Enterprise liunx5&period;4虚拟机安装10G RAC实验&lpar;二&rpar;

    接第一篇 http://www.cnblogs.com/myrunning/p/3993824.html 3.集群方面的配置 3.1配置hosts文件 此配置需要在两个节点都要配置. 3.2配置 Ha ...

  3. 【ADO&period;NET】5、手机归属地查询&lpar; winfrom &rpar;

    using System.IO; 有一个数据库手机号码的txt文件,格式是 : 13500000000-13560000000-中国移动 查询结果: 湖南移动[邵阳]文件夹选择对话框 FolderBr ...

  4. MySQL协议简单分析

     tcpdump -i eth0 -s0  -l -w - port 3306|strings|grep -i -E 'select|update|insert|delete|set' 

  5. git:fatal the current branch master has no upstream branch

    git push的时候发生上述错误. git push -u "resp" master resp为git仓库的“地址” reference中由解决方案 http://blog.c ...

  6. touch修改文件的修改时间和访问时间&comma;ls --full-time显示文件详细,stat命令

    1. 同时修改文件的修改时间和访问时间 touch -d "2010-05-31 08:10:30" test.doc 2. 只修改文件的修改时间 touch -m -d &quo ...

  7. 在Openstack上创建并访问Kubernetes集群

    第一部分:创建集群 在Openstack部署Kubernetes集群运行Nginx容器的步骤,其中包括: 利用Murano部署Kubernetes集群 配置Openstack的安全性使Kubernet ...

  8. 入侵检测工具之RKHunter &amp&semi; AIDE

    一.AIDE AIDE全称为(Adevanced Intrusion Detection Environment)是一个入侵检测工具,主要用于检查文件的完整性,审计系统中的工具是否被更改过. AIDE ...

  9. 防cc攻击策略

    黑客攻击你的网站,会采取各种各样的手段,其中为了降低你网站的访问速度,甚至让你的服务器瘫痪,它会不断的刷新你的网站,或者模拟很多用户同一时间大量的访问你的网站, 这就是所谓的CC攻击,这就需要我们在程 ...

  10. Linux debug

    proc文件系统中可以查看一些正在运行的变量如device-tree sh-3.2# cat /proc/device-tree/ #address-cells fixedregulator@9/ # ...