hdu2476String painter (区间DP)
2024-08-31 08:28:16
Problem Description
There are two strings A and B with equal length. Both strings are made up of lower case letters. Now you have a powerful string painter. With the help of the painter, you can change a segment of characters of a string to any other
character you want. That is, after using the painter, the segment is made up of only one kind of character. Now your task is to change A to B using string painter. What’s the minimum number of operations?
character you want. That is, after using the painter, the segment is made up of only one kind of character. Now your task is to change A to B using string painter. What’s the minimum number of operations?
Input
Input contains multiple cases. Each case consists of two lines: The first line contains string A. The second line contains string B. The length of both strings will not be greater than 100.
Output
A single line contains one integer representing the answer.
Sample Input
zzzzzfzzzzz
abcdefedcba
abababababab
cdcdcdcdcdcd
Sample Output
6
7题意:给定两个字符串a和b,求最少须要对a进行多少次操作,才干将a变成b。每次操作时将a中随意一段变成随意一个字母所组成的段。#include<stdio.h>
#include<string.h>
int min(int a,int b)
{
return a>b? b:a;
}
int main()
{
int dp[105][105],ans[105];
char a[105],b[105];
while(scanf("%s%s",a,b)>0)
{
int len=strlen(a);
memset(dp,0,sizeof(dp));
for(int r=0;r<len;r++)
for(int i=0;i<len-r;i++)
{
int j=i+r;
dp[i][j]=dp[i+1][j]+1;
for(int k=i+1;k<=j;k++)
if(b[i]==b[k])
dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]);
}
for(int i=0;i<len; i++)
ans[i]=dp[0][i];
for(int i=0;i<len; i++)
if(a[i]==b[i])
{
if(i==0)ans[i]=0;
else ans[i]=ans[i-1];
}
else{
for(int k=0;k<i;k++)
ans[i]=min(ans[i],ans[k]+dp[k+1][i]);
}
printf("%d\n",ans[len-1]);
}
}
最新文章
- 自定义asp.net 脚手架(基架)
- 分布式缓存技术memcached学习(五)—— memcached java客户端的使用
- CC3000 主机驱动API介绍
- 学习Android,最简单的按钮提示文本信息
- Android各个版本代号及其特性
- MSSql得到表的结构和字段
- c++sort函数的用法浅析
- HTTP 504 错误
- how to use tar?
- OC继承以及实例变量修饰符
- Python dict 按键和值排序
- mysql自连接求累计金额
- Mybatis的分表实战
- tar.gz和tar.bz2
- dagScheduler
- win10+vscode部署java开发环境
- Python(六)之文件对象
- PLSQL Package包的使用
- 41F继电器座的解剖与妙用
- C#.NET常见问题(FAQ)-程序如何把窗体文件从从一个项目中复制到另一个项目
热门文章
- 如何提升SQL语句的查询性能
- [JXOI 2018] 守卫 解题报告 (DP)
- 记录,javascript中对象的属性名是字符串,却可以不用引号
- Endnote导入共享数据
- 2015 多校赛 第一场 1002 (hdu 5289)
- mvc中Html.AntiForgeryToken的作用和用法
- 抽象工厂模式(AbsFactory)C++实现
- RocketMQ之基本信息
- 【Oracle】DG中 Switchover 主、备切换
- RGB_D_开发征程(使用Kinect)