首页 > 代码库 > HDU 3001 状压DP
HDU 3001 状压DP
有道状压题用了搜索被队友骂还能不能好好训练了，，
hdu 3001 经典的状压dp
大概题意。。有n个城市 m个道路 成了一个有向图。n<=10； 然后这个人想去旅行。有个超人开始可以把他扔到任意的一个城市。。然后他就在城市之间游荡。要满足他要游玩所有的城市。。并且。每个城市最多去两次。要求路程最短。。如果他不能游完所有的城市，，那么。。就输出-1 否则 输出最短距离
如果用搜索。。。不靠谱 然后用搜索，，
怎么压缩？？ 用一个整型数 i 表示他现在的状态。。显然一个城市是要用两位。。00 表示没去过 01 表示去了一次 10 表示去了两次 然后最多10个城市，。。那么一共用20位 2^20一共是。。1024*1024 也就是10^6大概吧。。 然后dp[i][j] 表示的是 当前这个状态。。并且 最后他在j城市的最短路径。。然后他可以去另外的城市 咋一看 这个时间复杂度是 。。10^6 * 10 * 10 然后加上各种判断。。还要开一个10^6 *10 的数组 然后就MLE 了，，我们发现 i 在自然数里面并不是连续的 而是离散的 我们 先找出满足条件的 i 存在一个数组inn里面 然后用二分查找 。。。相当于用了一个哈希表，，存了这么多的情况，，，然后就是dp转移了，，，，
MLE 1 wa1 : 没考虑输出-1 的情况
代码不长
#include <cstdio>#include <cmath>#include <algorithm>#include <iostream>#include <cstdlib>#include <string>#include <queue>#include <cstring>#define CL(a,b) memset(a,b,sizeof(a))#define ll __int64#define TEST cout<<"TEST ***"<<endl;#define INF 0x7ffffff0#define MOD 100000000using namespace std;int inn[1000010];int dp[101000][11];int gra[15][15];int n,m,cii;int bin(int s,int e,int v){ int mid=(s+e)/2; if(inn[mid]==v)return mid; if(inn[mid]>v)return bin(s,mid,v); else return bin(mid+1,e,v);}int initinn(){ int i,ctt=0,taginn,teminn; for(i=0;i<=1100000;i++) { teminn=i;taginn=1; while(teminn) { if((teminn&3)==3) { taginn=0; break; } teminn=teminn>>2; } if(taginn==1) { inn[ctt++]=i; } } return ctt;}int main(){ cii=initinn(); while(scanf("%d %d",&n,&m)!=EOF) { CL(gra,-1); int i,j,k,a,b,w; int rem=INF; int ma=(1<<(2*n))-1; for(i=0;i<m;i++) { scanf("%d %d %d",&a,&b,&w); if(gra[a][b]==-1||gra[a][b]>w) { gra[a][b]=gra[b][a]=w; } } CL(dp,-1); for(i=0;i<=n;i++)dp[0][i]=0; for(i=0;i<=n;i++)gra[0][i]=gra[i][0]=gra[i][i]=0; for(i=0;inn[i]<=ma;i++) { a=inn[i]; for(j=1;j<=n;j++) { if(dp[i][j]==-1)continue; for(k=1;k<=n;k++) { if(gra[j][k]==-1)continue; b=k-1; if(a&(1<<(2*b+1)))continue; w=a+(1<<(2*b)); w=bin(1,cii,w); if(dp[w][k]==-1||dp[w][k]>dp[i][j]+gra[j][k]) dp[w][k]=dp[i][j]+gra[j][k]; } b=1; w=a; for(k=1;k<=n;k++) { if((w&3)==0) { b=0; break; } w=w>>2; } if(b==1&&dp[i][j]<rem)rem=dp[i][j]; } } if(rem==INF)rem=-1; printf("%d\n",rem); } return 0;}
HDU 3001 状压DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。