POJ 1159 Palindrome-最长公共子序列问题+滚动数组(dp数组的重复利用)(结合奇偶性)
2024-09-04 05:51:27
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
题意:给出n,表示接下去给出的字符串长度为n,求最少插入几个字符可以使该字符串变成回文字串。
思路:设原字符串为a,反转该字符串设为b,用字符串长度减去a、b的最长公共子序列即可。
注意:
- 若用%c输入,记得getchar
- 即使利用了最长公共子序列中后,dp数组开[5050][5050]会造成内存超限,这时候需要利用滚动数组进行处理(结合奇偶性进行重复利用),由于我们只需要求出dp[n][n],所以前面部分的空间其实是可以重复利用的,比如说1->2存完之后,我们需要存3了,但是没有必要再去开辟空间,因为前面1所占的空间之后已经不需要再用了,所以我们可以将3存到1的位置,即3->1,以此类推 4->2。dp只需开到[2][5050]即可,即对每一部分i%2。
- 顺带注意区别一下子序列和字串,子序列是不要求满足连续性的,而字串是需要连续的。
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std; char a[],b[];
int dp[][];
int main()
{
int n;
cin>>n;
memset(dp,,sizeof(dp));
memset(a,'\0',sizeof(a));
memset(b,'\0',sizeof(b)); scanf("%s",a); int p=;
for(int i=n-; i>=; i--)
b[p++]=a[i]; for(int i=; i<n; i++)
{
for(int j=; j<n; j++)
{
if(a[i]==b[j])
dp[(i+)%][j+]=dp[i%][j]+;
else
dp[(i+)%][j+]=max(dp[i%][j+],dp[(i+)%][j]);
}
}
cout<<n-dp[n%][p]<<endl;
return ;
}
最新文章
- 【FLUENT案例】06:与EDEM耦合计算
- 错误:找不到请求的 .Net Framework Data Provider。可能没有安装.
- float和double精度问题
- 在线教学、视频会议 Webus Fox(2) 服务端开发手册
- 实际遭遇并解决:类型“ASP.global_asax”同时存在的问题
- .net,微软,薪资及其他
- JAVA使用HBASE常用方法
- VS2013试用期结束后如何激活
- BYTE、WORD与DWORD类型
- 使用atomic一定是线程安全的吗
- Gradle学习草稿
- 谈一谈Java8的函数式编程(二) --Java8中的流
- Java中的null值总结
- PHP开发中涉及到emoji表情的几种处理方法
- bootstrap 使用总结
- 利用阿里大于接口发短信(Delphi版)
- Oracle:使用二进制工具修改高版本的 exp (dump)文件,以便 低版本 imp 工具 导入
- 《DSP using MATLAB》Problem 4.1
- Control(拆点+最大流)
- ORA 00972 错误处理