转载请注明出处,谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove
继续IDA*,明显可以想到的一个剪枝是,至少还需要的长度是所有剩余长度的最大值,这样就可以根据深度和估价函数来剪枝,就可以用IDA*了。
开始竟然用状态压缩,枚举状态,果断超时,注释部分就是原先写的,其实每步都是贪心,如果取了某个位置的字母,其它字符串相同字符肯定一起取掉。
这样的话,状态就少了很多,1.6S,还可以。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<map>
#include<string>
#define inf 1<<30
#define eps 1e-7
#define LD long double
#define LL long long
#define maxn 1005
using namespace std;
int n,len[8];
int depth;
bool flag;
char dna[8][6];
int get_h(int *l){
int ans=0;
for(int i=0;i<n;i++)
ans=max(ans,l[i]);
return ans;
}
//bool check(int *l,int state){
// int ch=0;
// for(int i=0;i<n;i++)
// if(((1<<i)&state)==0)
// continue;
// else if(l[i]==0)
// return false;
// else if(ch==0||(int)dna[i][len[i]-l[i]]==ch)
// ch=(int)dna[i][len[i]-l[i]];
// else
// return false;
// return true;
//}
void IDAstar(int *l,int tmp_depth){
if(flag)
return;
if(get_h(l)>tmp_depth)
return;
if(tmp_depth==0){
flag=true;
return;
}
bool mark[8];
memset(mark,false,sizeof(mark));
for(int i=0;i<n;i++)
if(mark[i]==false&&l[i]){
int tmp[8];
for(int j=0;j<n;j++)
tmp[j]=l[j];
mark[i]=true;
char ch=dna[i][len[i]-l[i]];
tmp[i]--;
for(int j=i+1;j<n;j++)
if(!mark[j]&&dna[j][len[j]-l[j]]==ch&&l[j]){
mark[j]=true;
tmp[j]--;
}
IDAstar(tmp,tmp_depth-1);
}
/*for(int i=1;i<(1<<n);i++)
if(check(l,i)){
int tmp[8];
for(int i=0;i<8;i++)
tmp[i]=l[i];
for(int j=0;j<n;j++)
if(i&(1<<j))
tmp[j]--;
IDAstar(tmp,tmp_depth-1);
}*/
}
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
int low=0;
for(int i=0;i<n;i++){
scanf("%s",dna[i]);
len[i]=strlen(dna[i]);
low=max(low,len[i]);
}
flag=false;
for(depth=low;;depth++){
IDAstar(len,depth);
if(flag){
printf("%d\n",depth);
break;
}
}
}
return 0;
}
分享到:
相关推荐
HDU-1711 Number Sequence(KMP算法)For each test case, you should output one line wh
包含实验内容:对应实验要求上的1/2/3/5实验,分别为setName/setNice,petree输出进程,模拟shell,进程通信,文件系统。包含全部实验源代码和详尽的word实验报告。同时包含在线PTA编程题目:进程模拟,模拟进程调度...
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
【hdu5306】Gorgeous Sequence 线段树区间最值操作-附件资源
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
搜索 dfs 解题代码 hdu1241
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu2101AC代码
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
杭州电子科技大学oj平台上的第1010题,是关于搜索的题目,很不错的题
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 1166线段树代码
HDU最全ac代码
hdu动态规划算法集锦
自己做的HDU ACM已经AC的题目