注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

【神DP】【BZOJ1080】[SCOI2008]劣质编码  

2014-05-04 19:46:49|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
@BZOJ1080: [SCOI2008]劣质编码
四川怎么净出神题啊……
这道DP太神了
我看了好久完全没有思路
最后果断看题解……结果题解只有三行QAQ看不懂
于是我就花了一晚上研究代码QAQ
然后又用了一上午调代码总算过了,WA得我快哭瞎了QAQ
恩tyvj的数据比较奇葩,换行需要多读一个'\r'
(还好我有数据)

另:还有一个问题我不太明白,二维的时候如果要输出字典序的方案要怎么搞……
有神犇会的话求讲一下,万分感谢Orz
------------------------------------------------------------------------------------------------------------------------------------------------
题解:
某神犇题解地址
关于二维的情况,这位神犇只说了一句,然后我发现二维的情况还不会TAT
然后发现这是之前测试的题目……于是去请教当时AC的Liangjs神犇
用BFS版的记忆化搜索
题解说是最短路大概是因为可以看成隐式图上的SPFA
就是规定一个模板串和匹配串,然后f[i][j]表示模板串i的前j个已经匹配
初始把所有f[i][0] i=1~n扔到队里,每次取队首元素进行状态转移
假设是f[i][j]
先枚举一个匹配串k,
如果其长度len[k]+j < len[i],转移到f[i][j+len[k]]
如果len[k]+j > len[i] 就转移到 f[k][len[i]-j]
如果len[k]+j == len[i]就更新答案
直到队空
然后就是蛋疼的三维情况……
一个模板串两个匹配串
为了保证状态不会混乱(?
要保证f[i][j][k]有j > k
但是比较蛋疼的是你要考虑不要让匹配串的构成相同
于是就要记录三个状态类型:
0:两个匹配串构成不同,可以更新答案
1:模板串和一个和它构成相同的匹配串和另一个较短的匹配串(2长1短)
2:和1类似,但是是(1长2短)
类型直接的转化关系
0->0
1->1/2
2->0/1/2
start->2
具体过程比较恶心,下面是代码……
注释是我研究标程的时候搞的
现在直接复制到我的代码上了……


#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
using namespace std;
typedef short BOOL;
const int N = 61;
const int _MAX = 1000000000;
int n,m,len[N];
int ans,dp[N][N][N][3];
char data[N][N];
BOOL cmp[N][N][N];
struct zht{
int a,i,j,t;
zht(){}
zht(int aa,int ii,int jj,int tt):a(aa),i(ii),j(jj),t(tt){}
};
queue<zht> dui;
int scan(){
char cc=' ';int re=0,fh=1;
while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='+'){fh=-1;cc=getchar();}
if(cc=='+'){fh=1;cc=getchar();}
while('0'<=cc&&cc<='9'){
re=re*10+cc-'0';
cc=getchar();
}
return re*fh;
}
int scans(char s[]){
char cc=' ';int i;
cc=getchar();
//*****数据非常恶心……行末可能有空格,这里不能加' '的判断,否则会WA三个点
for(i=1;!(cc=='\r'||cc=='\n');i++){
s[i]=cc;
cc=getchar();
}s[i]=0;
return i-1;
}
int main(){
int i,j,k;
n=scan();
for(i=1;i<=n;i++){
len[i]=scans(data[i]);
while(data[i][len[i]]==' ')data[i][len[i]--]=0;
if(len[i]==0){printf("0\n");return 0;}
}

//找出所有可以转移的位置
//也就是判断相等
for(i=1;i<=n;i++)
for(j=1;j<=n;j++){
for(k=0;k<len[i];k++){
int tmp=min(len[i]-k,len[j]),ii;
for(ii=1;ii<=tmp;ii++)
if(data[i][ii+k]!=data[j][ii]) break;
cmp[i][j][k] = ii>tmp;
}cmp[i][j][len[i]]=1;
}
for(i=0;i<=n;i++)
for(j=0;j<N;j++)
for(k=0;k<N;k++)
dp[i][j][k][0]=dp[i][j][k][1]=dp[i][j][k][2]=_MAX;
for(i=1;i<=n;i++){
dui.push(zht(i,0,0,2));
dp[i][0][0][2]=len[i];
}
ans=_MAX;
while(!dui.empty()){
zht now = dui.front(); dui.pop();
int aa,ii,jj,tt,l;
int &Dp = dp[now.a][now.i][now.j][now.t];
//另外匹配的两个串结构不同
if(!now.t){
//update ans
if(now.i==now.j&&now.i==len[now.a]){
if(dp[now.a][now.i][now.j][now.t]<ans)
ans=dp[now.a][now.i][now.j][now.t];
continue;
}
//枚举新的匹配串
for(i=1;i<=n;i++){
/*
[tt.a]
111111111
1111111
[i]
转移状态
*/
//tt.i > tt.j
//接到匹配位数少的那一个上
if(!cmp[now.a][i][now.j]) continue;tt=0;
//如果接超了,就把新接的串当成tt.a
if(len[i]+now.j > len[now.a]){
//由于等式的传递关系,长的匹配一定可以匹配到新串i上
//并且可以得到之前的串tt.a转换成的匹配一定比j长
aa=i;ii=len[now.a]-now.j;jj=now.i-now.j;
l=Dp + len[i] - (len[now.a]-now.j);
//否则只是更新一下长度
}else{
aa=now.a;ii=now.j+len[i];jj=now.i;
if(jj>ii)swap(jj,ii);
l=Dp;
}
//push
if(l < dp[aa][ii][jj][tt]){
dui.push(zht(aa,ii,jj,tt));
dp[aa][ii][jj][tt]=l;
}

}
//模板串和匹配i串结构相同
}else if(now.t==1){
//因为两个匹配结构相同,故不能更新答案
if(now.i==now.j&&now.i==len[now.a])continue;
//枚举新的匹配串
for(i=1;i<=n;i++){
//接到短的上
if(!cmp[now.a][i][now.j]) continue;
if(now.j+len[i] >= len[now.a]){
//如果接超了,就把新接的串当成tt.a
aa=i;ii=jj=len[now.a]-now.j;tt=2;
l=Dp + len[i] - ii;
}else{
aa=now.a;ii=now.i;jj=now.j+len[i];tt=1;
l=Dp;
}
//push
if(l < dp[aa][ii][jj][tt]){
dui.push(zht(aa,ii,jj,tt));
dp[aa][ii][jj][tt]=l;
}
}
//结构相同的两个匹配串
}else if(now.t==2){
for(i=1;i<=n;i++){
if(!cmp[now.a][i][now.i])continue;
//不要拿自己和自己匹配
if(now.i==0&&i==now.a) continue;
//一下放两个一样的
if(now.j+len[i] > len[now.a]){
aa=i;ii=len[i];jj=len[now.a]-now.j;tt=1;
l=Dp + len[i] - jj;
}else{
aa=now.a;ii=jj=now.i+len[i];tt=2;
l=Dp;
}
//push
if(l < dp[aa][ii][jj][tt]){
dp[aa][ii][jj][tt]=l;
dui.push(zht(aa,ii,jj,tt));
}
//枚举第二个匹配串
for(j=1;j<=n;j++){
//******能接上去********
if(!cmp[now.a][j][now.j]) continue;
//两个新匹配串不能是同一个串 ,但是内容需要相同
if(i==j)continue;
//能接上去
if(!cmp[i][j][0])continue;
int si=i,sj=j;
//若不相等保证 len[si] > len[sj]
//若长度相等且sj==当前串 则使si==当前串
if(len[sj] > len[si] || (len[si]==len[sj]&&sj==now.a)) swap(si,sj);
if(now.i+len[si] > len[now.a]){
if(now.j+len[sj] > len[now.a]){
aa=si;ii=len[sj];jj=len[now.a]-now.i;
l=Dp+ len[si]-jj;
tt=0;
}else{
aa=si;ii=len[now.a]-now.i;jj=len[sj];
l=Dp+len[si]-ii;
//sj和tt.a相同而si较长 仍是2状态
//***我不知道为啥这里一开始填的是 if(ii==jj)
if(now.a==sj&&now.i==0) tt=2;
else tt=0;
}
}else{
aa=now.a;ii=now.i+len[si];jj=now.i+len[sj];tt=0;
l=Dp;
if(now.i==0&&si==now.a){
if(jj<len[now.a])tt=1;
//相等
else{
aa=sj;ii=jj=len[sj];
tt=2;
}
}
}
if(l < dp[aa][ii][jj][tt]){
dp[aa][ii][jj][tt]=l;
dui.push(zht(aa,ii,jj,tt));
}
}
}
}
}
if(ans==_MAX)
printf("-1\n");
else
printf("%d\n",ans);
return 0;
}



  评论这张
 
阅读(766)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017