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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[TsinsenA1419][Codeforces 67C]Sequence of Balls  

2014-10-23 22:04:53|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

A1419. Sequence of Balls

据说清澄上全是神题

今天去找了道上面的CF题……然后被虐出翔Orz

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int scan(){int i=0;scanf("%d",&i);return i;}
const int N = 4000+10;
const int MAX = 1E9+10;
int n,m,co[4],f[N][N],la[2][N][30];
char str[2][N];
int main(){
int i,j,len[2];
//freopen("in.txt","r",stdin);
for(i=0;i<4;i++)co[i] = scan();
scanf("%s",str[0]+1);
scanf("%s",str[1]+1);
len[0] = strlen(str[0]+1);
len[1] = strlen(str[1]+1);
for(i=0;i<=len[0];i++)
for(j=0;j<=len[1];j++)
if(i || j)
f[i][j] = MAX;
for(i=1;i<=len[0];i++){
for(j='a';j<='z';j++)la[0][i][j-'a'] = la[0][i-1][j-'a'];
if(i>1)la[0][i][str[0][i-1]-'a'] = i-1;
}
for(i=1;i<=len[1];i++){
for(j='a';j<='z';j++)la[1][i][j-'a'] = la[1][i-1][j-'a'];
if(i>1)la[1][i][str[1][i-1]-'a'] = i-1;
}
for(i=0;i<=len[0];i++)
for(j=0;j<=len[1];j++)
if(i || j){
//del
if(i-1>=0)f[i][j] = min(f[i][j],f[i-1][j] + co[1]);
//add
if(j-1>=0)f[i][j] = min(f[i][j],f[i][j-1] + co[0]);
//change
if(i-1 >= 0 && j-1 >= 0){
if(str[0][i] == str[1][j]) f[i][j] = min(f[i][j],f[i-1][j-1]);
else f[i][j] = min(f[i][j],f[i-1][j-1] + co[2]);
}
int ii,jj;
ii = la[0][i][str[1][j]-'a'];
jj = la[1][j][str[0][i]-'a'];
if(ii&&jj)
f[i][j] = min(f[i][j],f[ii-1][jj-1] + (i - ii-1)*co[1] + (j - jj-1)*co[0] + co[3]);
}
printf("%d\n",f[len[0]][len[1]]);
return 0;
}

题解:

乍一看是很经典的DP……

但是有一个奇怪的交换操作,题里的限制条件很容易得到一个数不会被连续交换两次。

然后我就去很高兴地写了……写着写着越来越发现不对劲……有好多奇怪的情况

两种比较蛋疼的情况:

1.删除/插入了一段之后再交换

2.修改了前一个之后再交换

第二个情况可以证明一定不是最优

第一个情况很明显暴力转移会变成N3,而且插入的情况也比较奇怪

网上题解的解决方案是这样的:

首先把插入转换成在b中删除一段

然后可以得到对于多个相同的字符,一定是靠后的决策更优(改变少),所以对于每个位置记录上一个字符c('a'~'z')的位置,然后就可以DP了

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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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