Topcoder SRM 698 Div1 250 RepeatString(dp)
2024-08-29 09:12:55
题意
[题目链接]这怎么发链接啊。。。。。
Sol
枚举一个断点,然后类似于LIS一样dp一波
这个边界条件有点迷啊。。fst了两遍。。。
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10, INF = 1e9 + 7;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N, f[101][101];
class RepeatString{
public:
int solve(int pos, string s) {
string a, b; a += '.'; b += '*';
memset(f, 0x3f, sizeof(f));
for(int i = 0; i < pos; i++) a += s[i];
for(int i = pos; i < N; i++) b += s[i];
int la = a.length() - 1, lb = b.length() - 1;
f[0][0] = 0;
for(int i = 0; i <= la; i++) f[i][0] = i;
for(int i = 0; i <= lb; i++) f[0][i] = i;
for(int i = 1; i <= la; i++) {
for(int j = 1; j <= lb; j++) {
f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
f[i][j] = min(f[i][j], f[i - 1][j - 1] + (a[i] != b[j]));
}
}
return f[la][lb];
}
int minimalModify(string s) {
N = s.length(); int ans = N;
for(int i = 0; i < N; i++) ans = min(ans, solve(i, s));
return ans;
}
};
int main() {
string s;
cin >> s;
cout << RepeatString().minimalModify(s);
}
/*
pkafkbeabccfjejkdgkaatcedaocgmecaapakfvbfgefr
*/
最新文章
- 【转】iOS UIApplication详解
- Eclipse设置黑色主题
- 拦截js方法备忘录
- jquery基本选择器id
- block的用法以及block和delegate的比较(转发)
- DES加密解密帮助类
- 简单的 jQuery 浮动层随窗口滚动滑动插件实例
- 数据结构与算法--Boyer-Moore和Rabin-Karp子字符串查找
- ACTION_NAME等常量 不能在模板里直接取值?
- C# 泛型单例
- AnjularJs教程
- org.apache.http.client.ClientProtocolException: URI does not specify a valid host name
- Windows平台下结合 tortoiseSVN 和 VisualSVN Server 搭建SVN服务器并实现 web 站点同步
- MAC环境配置
- sql server 索引阐述系列五 索引参数与碎片
- WIN10平板 总是提示你需要管理员权限怎么办
- [dpdk] SDK编译-简单扼要版
- WPF:数据和行为
- 微信图片分享遇到 checkArgs fail, thumbData is invalid
- tomcat设置debug模式
热门文章
- time、random以及序列化模块
- Array数组结构底层实现复习
- Query on a tree 树链剖分 [模板]
- C语言学习总结(1)——结构体
- Not all processes could be identified, non-owned process info will not be shown, you would have to be root to see it all.
- Visual Studio 2019 秘钥
- C++_类继承5-抽象基类
- [JLOI2015]管道连接(斯坦纳树)
- Luogu P1801 黑匣子_NOI导刊2010提高(06)
- loj 2038 / 洛谷 P4345 [SHOI2015] 超能粒子炮・改 题解