UVa1630,Folding
2024-10-20 00:32:42
区间dp,记忆化搜就可以
st为原串
dp[p][q]存st[p]~st[q]的最优长度,f[p][q]存对应的最优串
从(0,len-1)开始搜,f[0][len-1]为所求ans,回溯条件为p==q
同前两个题思路极为类似,但是我发现这3个题放到一起真的非常的好,难度递进,依次难在地方就是状态转移的时候决策的寻找
而此题的决策不是很明确,可以理解为两个决策吧(大家都这么认为= =但我不怎么赞同)
1:当子串st[p~q]可以折叠
2:将st[p~q]分成两段
二者中取最短
(其实第二个决策隐藏了一个决策,举个例子,原串AA,而压缩成2(A)显然是不对的,根据第二个决策,dp[AA]=dp[A]+dp[A]=2优于决策1)
自己coding时遇到一个问题:
NTTTTTNTTTTTNTTTTT
根据决策2,会得到一种情况f[0][len-1]=2(N5(T))N5(T),怎么折叠成3(N5(T));
若是根据决策1,那得到的结果会是3(NTTTTT);
特殊处理嵌套会非常麻烦
解决方法详见代码
观察了网上其他人的代码,学到了不少东西
coding+debug:差不多断断续续5个小时左右(但是这5个小时是比较值的,记忆化dp或者说区间dp这一方面我理解的更具体,更深刻了)
/*
* Author: Bingo
* Created Time: 2015/3/3 14:19:57
* File Name: uva1630.cpp
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <time.h>
using namespace std;
const int maxint = ;
int n;
int len;
string st;
int dp[][];
string f[][];//一层状态对应一个串
int judge(int l,int r){
for(int i=;i<=(r-l+)/;i++){
if((r-l+)%i)continue;
bool flag=true;
for(int j=l;j+i<=r;j++){
if(st[j]!=st[j+i]){
flag=false;
break;
}
}
if(flag)return i;
}
return false;
}
int solve(int p,int q){
if (dp[p][q]) return dp[p][q];
else if(p==q) {
f[p][q]=st[p];
dp[p][q]=;
return ;
}
else {
int ans=maxint;
int res;
int k;
for (int i=p;i<q;i++){
res=solve(p,i)+solve(i+,q);
if (ans>res){
ans=res;
k=i;
}
}
f[p][q]=f[p][k]+f[k+][q];//此时的f[p][q]是否可折叠等价于st[p] [q]是否可折叠,巧妙的解决折叠f[p][q]时提取公因式的困难
int t=judge(p,q);
if (t){
char tt[];
sprintf(tt,"%d",(q-p+)/t);
string newstr=tt+string("(")+f[p][p+t-]+string(")");//f[p][p+t-1]是精髓所在
if (newstr.size()<f[p][q].size()) f[p][q]=newstr;
}
dp[p][q]=f[p][q].size();
return dp[p][q];
}
}
int main () {
while (cin>>st){
len=st.size();
memset(dp,,sizeof(dp));
solve(,len-);
cout << f[][len-]<<endl;
}
return ;
}
最新文章
- 网站指纹识别工具——WhatWeb v0.4.7发布
- 检查或遍历android手机应程
- 父元素与子元素之间的margin-top问题
- firefox和chrome对于favicon.ico关于content-security-policy的不同处理
- (三)映射对象标识符(OID)
- windows驱动开发推荐书籍
- wpf 自定义依赖性属性 作用之一 对数据绑定的支持
- mongodb教程二
- 有一个NSStirng类型,retain时尚宣言name财产setter内部方法的每一行代码的作用?
- SVN和Git的一些用法总结(转)
- Time complexity of ArrayList in Java
- java SWT嵌入IE,SafeArray .
- 自动化双向数据绑定AngularJs---入门
- c/c++ 贪吃蛇控制台版
- 剑指Offer——网易笔试之不要二——欧式距离的典型应用
- Shell脚本-自动化部署WEB
- js实现页面重定向
- python 利用tkinter模块设计出window窗口(搞笑版)
- 几个C++ online test 网站
- SpringBoot日记——Redis整合
热门文章
- 201521123040 《Java程序设计》第6周学习总结
- 201521123048《Java程序设计》第6周学习总结
- 201521123003《Java程序设计》第4周学习总结
- 我的Emacs配置文件
- 201521123110《Java程序设计》第14周学习总结
- 201521123104《java程序设计》第13周学习总结
- 201521123081《Java程序设计》 第9周学习总结
- Spring详解(六)------AOP 注解
- Rigidbody(刚体) and Collider(碰撞器)
- python generator(生成器)