1159--Palindrome(dp:回文串变形2)
2024-08-30 23:28:18
Palindrome
Time Limit: 3000MS | Memory Limit: 65536K | |
Total Submissions: 53431 | Accepted: 18454 |
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.
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.
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
还有一种dp的方法,dp[l][i],表示长度为l的以第i个字符開始的字符串须要多少操作。
对于长度为1的字符串,操作为0
长度为2的字符串,假设两个字符同样,操作为0,不同操作为1
长度为3的字符串。假设左右同样,操作为0。左右不同,对于a[1],a[2],a[3]来说 能够在前面添加a[3],或后面添加a[1],那么就仅仅须要推断剩余的两和字符须要的操作了。
长度为4的字符串,左右同样,那么须要求中间的两个字符,不同的话和长度为3的推断方式同样。
得到 长度为l開始为i的串能够由, 长度为l-1開始为i的,长度为l-1開始为i+1的。或者是长度为l-2,開始为i+1的变化得到。
推出dp公式
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int dp[3][5100] ;
char str[5100] ;
int main()
{
int i , l , k1 , k2 , k3 , n ;
while(scanf("%d", &n) !=EOF)
{
scanf("%s", str);
for(i = n ; i >= 0 ; i--)
str[i] = str[i-1] ;
k1 = -1 ; k2 = 0 ; k3 = 1;
memset(dp,0,sizeof(dp));
for(l = 2 ; l <= n ; l++)
{
k3++ ;
if(k3 == 3) k3 = 0 ;
if(k3 == 0){ k2 = 2 ; k1 = 1 ; }
else if( k3 == 1 ){ k2 = 0 ; k1 = 2 ; }
else { k2 = 1 ; k1 = 0 ; }
for(i = 1 ; i <= n-l+1 ; i++)
{
if( str[i] == str[i+l-1] )
dp[k3][i] = min( min(dp[k2][i]+1,dp[k2][i+1]+1),dp[k1][i+1] ) ;
else
dp[k3][i] = min( dp[k2][i]+1 , dp[k2][i+1]+1);
}
}
printf("%d\n", dp[k3][1]);
}
return 0;
}
最新文章
- 转:POI操作Excel导出
- EF 的 霸气配置,秒杀一切
- iOS 开发之SVN提交问题解决
- C# in depth学习(1)
- CSS中的text-overflow:clip|ellipsis的使用
- php发展起源
- ZooKeeper日志与快照文件简单分析
- Ninx虚拟主机的配置
- 多比Web 3D展示(3D机房/3D监控)中间件多比Web 3D展示(3D机房/3D监控)中间件免费下载购买地址
- 中文圣经 for Android
- [转]MAC下JDK版本的切换
- 深入理解object C中复制对象的用法(二)
- 常用文件的文件头(附JAVA测试类)
- PHP简单socket编程
- HDU5874
- [Tarjan 学习笔记](无向图)
- Dynamics Customer Engagement V9版本配置面向Internet的部署时候下一步按钮不可点击的解决办法
- bootstrap的引用和注意事项
- java将秒转换为时分秒工具类
- Open-Drain与Push-Pull【转】