hdu-1513-Palindrome

简介: hdu-1513-Palindrome


Palindrome

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4052    Accepted Submission(s): 1377


Problem Description

A palindrome is a symmetrical string, that is, a string read identically from left to right as well as from right to left. You are to write a program which, given a string, determines the minimal number of characters to be inserted into the string in order to obtain a palindrome.

As an example, by inserting 2 characters, the string "Ab3bd" can be transformed into a palindrome ("dAb3bAd" or "Adb3bdA"). However, inserting fewer than 2 characters does not produce a palindrome.

 


Input

Your program is to read from standard input. The first line contains one integer: the length of the input string N, 3 <= N <= 5000. The second line contains one string with length N. The string is formed from uppercase letters from 'A' to 'Z', lowercase letters from 'a' to 'z' and digits from '0' to '9'. Uppercase and lowercase letters are to be considered distinct.

 


Output

Your program is to write to standard output. The first line contains one integer, which is the desired minimal number.

 


Sample Input

5 Ab3bd

 


Sample Output

2

 


Source

IOI 2000



题目分析:

意思就是让你在一个字符串中添几个字符让这个字符串成为回文串        这你要理解  lcs    如果明白了lcs是怎么查最长子序列的话就很好办了

比如说   123     321    用lcs 查一遍等于len=1              123321       这个串就是回文  但是我刚开始的思路就是把  123321  分成   123     321    两个串查他们的公共子串 然后总长度 6-2*len=4   但是这个串应该是0 的。然后我又看了看lcs     发现   abcsff      cbaiik    这个查出来是1     abcsff     iiabck   这个查出来就是  3    该是对lcs的理解就是错的我理解成有多少个相同字符就是多少呢!

那么知道了lcs 是怎么查的这个就好办了,只需把原串倒序一下  对这两个进行查找就行了,如果是回文串结果肯定是总长度了 如果不是回文那么查出的就是公共子串的长度那么    总长度减去公共长度及时需要添的了                                       比如 abcf  g cbah    倒置之后是    habc g fcba    红色部分和绿色部分只能查出有个长度为1的子串(上边已经说过lcs是怎么查的了)那么倒置后就相当于红色部分对红色部分查那么在纸上掩饰一边查找的结果应该是 5    abcg 一个长4 还有 cbah   对cbah  查出一个共5个  9-5=4   那么这个在添  4个就是回文了看看是不是



另外这个数据有点大需要用滚动数组   下边是看别人的滚动数组解析



相信很多同学都学过时间复杂度,在以前的很多程序编译里面我们也都看到过时间复杂度的优化,因为这个是一个很重要的因素,而且一般的ACM题目都是卡的时间,卡空间复杂度的不是很多,但是这里就卡了空间复杂度,这里我们介绍一种优化空间复杂度的方法——滚动数组。

下面首先介绍一下这个思想:滚动数组很适合用在二维DP而且是数组在很大时,可以节省内存,消除超内存的隐患!具体思想还是看了网上的资料,转载一个,共同享用吧!

滚动数组 举个简单的例子:

int i,d[100];

d[0]=1;d[1]=1;

for(i=2;i<100;i++)

d[i]=d[i-1]+d[i-2];

printf("%d",d[99]);

上面这个循环d[i]只需要解集中的前2个解d[i-1]和d[i-2];

为了节约空间用滚动数组的方法

int d[3];

d[0]=1;d[1]=1;

for(i=2;i<100;i++)

d[i%3]=d[(i-1)%3]+d[(i-2)%3];

printf("%d",d[99%3]);


注意上面的运算,我们只留了最近的3个解,数组好象在“滚动”一样,所以叫滚动数组


对于二维数组也可以用这种方法 例如:

int i,j,d[100][100];

for(i=1;i<100;i++)

   for(j=0;j<100;j++)

       d[i][j]=d[i-1][j]+d[i][j-1];


上?的d[i][j]忪便赖于d[i-1][j],d[i][j-1];

迿用滚动数组

int i,,j,d[2][100];

for(i=1;i<100;i++)

   for(j=0;j<100;j++)

       d[i%2][j]=d[(i-1)%2][j]+d[i%2][j-1];


#include<cstdio>
#include<cstring>
#define max(a,b)  (a>b?a:b)
int main()
{
  int n;
  while(~scanf("%d",&n))
  {
    int dp[2][5010];
    char str1[5010],str2[5010];
    scanf("%s",str1);
      strcpy(str2,str1);  
        strrev(str2);  //  strrev( ) c里面的倒置函数 
        memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++)
       for(int j=1;j<=n;j++)
       {
           if(str1[i-1]==str2[j-1])
              dp[i%2][j]=dp[(i-1)%2][j-1]+1;
            else  dp[i%2][j]=max(dp[(i-1)%2][j],dp[i%2][j-1]);
       }
       printf("%d\n",n-dp[n%2][n]);
  }
  return 0;
}



目录
相关文章
|
分布式计算 DataWorks 关系型数据库
MaxCompute产品使用合集之可以使用什么方法将MySQL的数据实时同步到MaxCompute
MaxCompute作为一款全面的大数据处理平台,广泛应用于各类大数据分析、数据挖掘、BI及机器学习场景。掌握其核心功能、熟练操作流程、遵循最佳实践,可以帮助用户高效、安全地管理和利用海量数据。以下是一个关于MaxCompute产品使用的合集,涵盖了其核心功能、应用场景、操作流程以及最佳实践等内容。
|
存储 缓存 安全
阿里云服务器实例规格选择参考:经济型、通用算力型、计算型、通用型、内存型区别
当我们在通过阿里云的各种活动选择云服务器实例规格的时候会发现,相同配置的云服务器往往有多个不同的实例可选,而且价格差别也比较大,这会是因为不同实例规格的由于采用的处理器不同,底层架构也有所不同(例如X86 计算架构与Arm 计算架构),因此不同实例的云服务器其性能与适用场景是有所不同。目前阿里云的活动中,主要的实例规格可分为经济型、通用算力型、计算型、通用型、内存型,对于很多初次接触阿里云服务器的用户来说,了解他们之间的差别就是比较重要的了,下面小编来为大家简单介绍下它们之间的区别。
阿里云服务器实例规格选择参考:经济型、通用算力型、计算型、通用型、内存型区别
|
iOS开发
App备案与iOS云管理式证书 ,公钥及证书SHA-1指纹的获取方法
App备案与iOS云管理式证书 ,公钥及证书SHA-1指纹的获取方法
1342 0
App备案与iOS云管理式证书 ,公钥及证书SHA-1指纹的获取方法
|
人工智能 搜索推荐
AIGC产品在教育领域的实践策略
【1月更文挑战第5天】AIGC产品在教育领域的实践策略
413 3
AIGC产品在教育领域的实践策略
|
监控 网络协议 Linux
|
关系型数据库 Serverless 分布式数据库
评测|PolarDB MySQL 版 Serverless
评测|PolarDB MySQL 版 Serverless PolarDB Serverless构建了一个全新的数据库形态,这种情况下,CPU和内存资源因其池化其使用率将会大幅度提升,云原生数据的成本将会远低于自建和RDS等一体化数据库,云原生技术的价值将会得到充分的体现。Serverless数据库能够使得数据库集群资源随客户业务负载动态弹性扩缩,将客户从复杂的业务资源评估和运维工作中解放出来。下面我尝试从几个维度对PolarDB的Serverless能力进行产品测评。
1086 0
评测|PolarDB MySQL 版 Serverless
|
存储 Kubernetes 开发工具
程序与技术分享:12.PV、PVC、StrageClass、本地持久存储
程序与技术分享:12.PV、PVC、StrageClass、本地持久存储
129 0
|
安全 C语言
四步手把手教你实现扫雷游戏(c语言)
四步手把手教你实现扫雷游戏(c语言)
191 0
ROS创建工作空间添加包并编译
ROS创建工作空间添加包并编译
415 0
|
关系型数据库 MySQL
mysql列名名称包含特殊字符的处理
上问题    不做处理的话会报错,识别不了 处理方式就是 需要把列名以反引号“`”(一般键盘的左上角数字1左边的那个键)来处理。 即查询语句为 欢迎大家一起说出自己的想法。
2813 0