HDU2476 String painter
题意
String painter
Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6669 Accepted Submission(s): 3230
The first line contains string A.
The second line contains string B.
The length of both strings will not be greater than 100.
zzzzzfzzzzz abcdefedcba abababababab cdcdcdcdcdcd
6 7
分析
参照AndyQsmart的题解。
读完题首先会想到的自然是用区间dp,但是列出来发现,没办法区间合并。因为一旦需要考虑对某一段成段染色的话,在区间合并的时候,就无法考虑转移过程中起始串的变化了。
既然这样,就不考虑成段染色造成的影响了,就当起始串和目标串处处不想等。
那么考虑区间[i, i+len],
自然遍历子区间[i, j],
如果[i, j]和[j+1, i+len]需要合并的话,
如果考虑成段染色的话,只有str2[i] == str2[j+1]时,考虑成段染色[i, j+1],但是[i, j+1]的父区间又有可能会成段然和str2[i]一样的颜色,所以不能直接将区间缩短成[i+1, j]和[j+2, i+len],所以可以考虑这一步的效果只相当于染str2[j+1]的时候,可以少染一个str2[i]。那么区间就变成[i+1, j]和[j+1, i+len], 这样父区间中可能再次出现一个i`,和j+1产生成段染色,即
p[i][i+len] = min(p[i][i+len], p[i+1][j]+p[j+1][i+len]);
然后就是考虑使用p来计算ans[i],表示前i个字符从起始串到目标串的步数。
ans[0]自然好考虑,只需要判断一下str1[0]和str2[0]。
对于ans[i],
如果str1[i] == str2[i],自然就可以退化成ans[i-1]。
其它情况,自然是遍历子区间ans[j]和p[j+1][i]进行合并。
时间复杂度\(O(n^3)\)
代码
#include<iostream>
#include<cstring>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
rg T data=0,w=1;
rg char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') w=-1;
ch=getchar();
}
while(isdigit(ch))
data=data*10+ch-'0',ch=getchar();
return data*w;
}
template<class T>il T read(rg T&x){
return x=read<T>();
}
typedef long long ll;
char str1[105],str2[105];
int n,p[105][105],ans[105];
void work(){
for(int i=0;i<n;++i) p[i][i]=1;
for(int len=1;len<n;++len)
for(int i=0;i<n&&i+len<n;++i){
p[i][i+len]=p[i+1][i+len]+1;
for(int j=i;j<i+len;++j)if(str2[i]==str2[j+1])
p[i][i+len]=std::min(p[i][i+len],p[i+1][j]+p[j+1][i+len]);
}
ans[0]=str1[0]==str2[0]?0:1;
for(int i=1;i<n;++i){
ans[i]=str1[i]==str2[i]?ans[i-1]:p[0][i];
for(int j=0;j<i;++j)
ans[i]=std::min(ans[i],ans[j]+p[j+1][i]);
}
printf("%d\n",ans[n-1]);
}
int main(){
// freopen(".in","r",stdin),freopen(".out","w",stdout);
while(~scanf("%s%s",str1,str2)){
n=strlen(str1);
work();
}
return 0;
}
最新文章
- Android之自定义侧滑菜单
- Latex制作beamer
- 我所了解的chrome
- 51nod1006(lcs)
- [Error Code: 1290. The MySQL server is running with the --secure-file-priv option so it cannot execute this statement]错误解决
- Find them, Catch them(POJ 1703 关系并查集)
- 常见 wifi热点的linux 驱动
- java regex possissive relunctant
- 解析STL中典型的内存分配
- java做单用户的多重并发会话数限制
- EXT 结构解析
- Javascript初识之流程控制、函数和内置对象
- day17 python递归案例(二分查找,三级菜单)
- 移动App专项测试
- 在Mac OS环境下安装MySQL服务
- getservbyname和getservbyport
- html网页如何使用哪种浏览器内核渲染的选择
- php代码覆盖率执行
- lua -- io.pathinfo
- c++ 判断容器A是否是容器B的子集,如果是,返回true(includes)
热门文章
- English trip -- VC(情景课)9 A Get ready
- ubuntu下使用CAJ云阅读--CAJViewer(Cloud)
- Working routine CodeForces - 706E (链表)
- Java字符串 API
- C++中的this指针
- nyoj1272表达式求值(递归法)
- SQL语句增加列、修改列类型、修改列、删除列
- After reading a picture than out a picture
- springboot + swagger的实体类属性注解
- Python笔记初识