HDU2476 String painter(DP)
2019-08-16 07:50:21来源:博客园 阅读 ()
HDU2476 String painter(DP)
题目
String painter
给出两个字符串s1,s2。对于每次操作可以将 s1 串中的任意一个子段变成另一个字符。问最少需要多少步操作能将s1串变为s2串。
解析
太妙了这个题,mark一下。
这个题先考虑怎么由空串转化s2,
\(f[i][j]\)表示从空串到s2最少的次数,
则有\(f[i][j]=s[i+1][j]+1\),
若\([i+1,j]\)存在一个\(k\),使\(s2[i]==s2[k]\),则\(f[i][j]=min\{f[i+1][k]+f[k+1][j]\}\),
\(k\)为断点,\(i\)和\(k\)同时刷。
然后再考虑把s1刷成s2的代价
设\(sum[i]\)表示把\(s1[1,i]\)刷成\(s2[1,i]\)的次数
当\(s1[i]==s2[i]\)时,可以不刷,显然\(sum[i]=sum[i-1]\)
否则,在区间内找最小次数\(sum[i]=min\{sum[j]+f[j+1][i]\}\)
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int n, m;
int f[N][N], sum[N];
char s[N], t[N];
int main() {
while (cin >> s) {
cin >> t;
memset(f, 0, sizeof f);
memset(sum, 0, sizeof sum);
int len = strlen(s);
for (int i = 0; i < len; ++i) f[i][i] = 1;
for (int i = 0; i < len; ++i)
for (int j = i - 1; j >= 0; --j) {
f[j][i] = f[j + 1][i] + 1;
for (int k = j + 1; k <= i; ++k) if (t[j] == t[k])
f[j][i] = min(f[j][i], f[j + 1][k] + f[k + 1][i]);
}
for (int i = 0; i < len; ++i) sum[i] = f[0][i];
if (s[0] == t[0]) sum[0] = 0;
for (int i = 1; i < len; ++i) {
if (s[i] == t[i]) sum[i] = min(sum[i], sum[i - 1]);
else for (int j = 0; j < i; ++j) sum[i] = min(sum[i], sum[j] + f[j + 1][i]);
}
cout << sum[len - 1] << endl;
}
}
原文链接:https://www.cnblogs.com/lykkk/p/11191725.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:题解:雇佣计划
- 复习C++语法--string与string_view 2020-05-28
- STL之<string> 2020-04-05
- 【题解】Building Strings Gym - 102152E 2020-03-31
- CodeForces 1320D - Reachable Strings 2020-03-20
- QT5中Json文件与QString的相互转化 2020-03-19
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash