首页 > 代码库 > hdu 5067 Harry And Dig Machine (状态压缩dp)
hdu 5067 Harry And Dig Machine (状态压缩dp)
题目链接
bc上的一道题，刚开始想用这个方法做的，因为刚刚做了一个类似的题，但是想到这只是bc的第二题，
以为用bfs水一下就过去了，结果MLE了，因为bfs的队列里的状态太多了，耗内存太厉害。
题意：
从某一点出发，遍历网格上的一些点，每个点至少访问一次需要的最小时间是多少。
官方题解：
由于Harry的dig machine是无限大的，而装载石头和卸载石头是不费时间的，所以问题可以转化成：从某一点出发，遍历网格上的一些点，每个点至少访问一次需要的最小时间是多少。这就是经典的旅行商问题，考虑到我们必须要遍历的点只有不到10个，可以用状态压缩解决。Dp[i][j]表示i状态的点被访问过了，当前停留在点j 需要的最少时间。枚举另一点不在i状态内的点k，从点j节点走向点k，状态转移Dp[i|(1?k)][k]=min(Dp[i|(1?k)][k],Dp[i][j]+Dis(j,k))其中Dis(j,k)表示点j与点k的最短距离，这个可以通过坐标O(1)计算得到。若有t个点包含石头，则算法复杂度为O(n∗m+(t2)∗(2t))。1 #include <iostream> 2 #include <cstdio> 3 #include <cmath> 4 #include <queue> 5 #include <cstring> 6 #include <cstdlib> 7 #include <algorithm> 8 #define LL __int64 9 #define INF 0x3f3f3f3f10 const int maxn = 50+10;11 using namespace std;12 struct node13 {14 int x, y;15 } p[maxn];16 int a[maxn][maxn], c[maxn][maxn], d[(1<<11)+10][15];17 18 int main()19 {20 int i, j, k, n, m, cnt;21 while(~scanf("%d%d", &n, &m))22 {23 memset(d, INF, sizeof(d));24 cnt = 0;25 for(i = 0; i < n; i++)26 for(j = 0; j < m; j++)27 {28 scanf("%d", &a[i][j]);29 if(i == 0 && j == 0)30 {31 p[cnt].x = i;32 p[cnt++].y = j;33 }34 else if(a[i][j]>0)35 {36 p[cnt].x = i;37 p[cnt++].y = j;38 }39 }40 for(i = 0; i < cnt; i++)41 {42 for(j = i+1; j < cnt; j++)43 {44 c[i][j] = c[j][i] = abs(p[i].x-p[j].x)+abs(p[i].y-p[j].y);45 }46 c[i][i] = 0;47 }48 d[0][0] = 0;49 for(i = 0; i < (1<<cnt); i++)50 {51 for(j = 0; j < cnt; j++)52 if(d[i][j]!=INF) //注意保证该状态存在53 for(k = 0; k < cnt; k++)54 {55 if(i&(1<<k)) continue; //注意保证该点还没有加入56 if(c[j][k]==INF) continue; //两个点之间可达57 d[i|(1<<k)][k] = min(d[i|(1<<k)][k], d[i][j]+c[j][k]);58 }59 }60 int ans = INF;61 for(i = 0; i < cnt; i++)62 ans = min(d[(1<<cnt)-1][i]+c[0][i], ans);63 cout<<ans<<endl;64 }65 return 0;66 }
hdu 5067 Harry And Dig Machine (状态压缩dp)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。