HDU2476 String painter(DP)
2024-08-30 20:45:30
题目
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;
}
}
最新文章
- Linux SendMail服务启动慢总结
- 简单的词法分析和语法分析(C++实现,CodeBlocks+GCC编译)
- Flask最佳实践
- 不支持C++11 decltype的噩耗
- git两种合并方法 比较merge和rebase
- MVC 发布
- 理解js中的自由变量以及作用域的进阶
- vsftpd 搭建与介绍
- Android:@id和@+id
- PHP中的设计模式:单例模式(译)
- 【转】Android开源项目发现---ListView篇(持续更新)
- Android 音乐播放
- 截取ip 不加引号
- JDK动态代理深入理解分析并手写简易JDK动态代理(下)
- 安晓辉大神的感悟:如果你发现了自己的学习模式,愿意学并且能坚持,我觉得没什么能阻挡你征服软件世界的脚步(对于开发人员来讲,最大的风险是:在职业规划上没有延续性地乱跳槽。时刻要牢记在心的:培养自己的稀缺性) good
- Node.js 串口通讯 node-serialport 使用说明
- kafka集群管理工具kafka-manager部署安装
- mysql 中语句执行的顺序以及查询处理阶段的分析
- python3 win10_x64 安装pcapy
- csc命令
热门文章
- Gamma阶段第一次scrum meeting
- Object changed by Unknown
- php 对接微信接口 {";errcode";:41001,";errmsg";:";access_token missing hint
- Centos 7.x卸载ibus黑屏修复及fcitx搜狗拼音安装方法
- 信息熵 Information Entropy
- wikiquote
- yum提示problem making ssl connection的解决办法
- ImportError: this is MySQLdb version (1, 2, 5, &#39;final&#39;, 1), but _mysql is version (1, 4, 4, &#39;final&#39;, 0)
- 使用gevent包实现concurrent.futures.executor 相同的公有方法。组成鸭子类
- Centos各版本系统ISO镜像下载地址