HDU 5067 Harry And Dig Machine（状压dp）

本文主要是介绍HDU 5067 Harry And Dig Machine（状压dp），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

HDU 5067 Harry And Dig Machine

思路：由于点才10个，在加上一个起点，处理出每个点之间的曼哈顿距离，然后用状压dp搞，状态表示为：
dp[i][s]，表示在i位置，走过的点集合为s的最小代价

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;const int N = 15;
int n, m;struct Point {int x, y;Point() {}Point(int x, int y) {this->x = x;this->y = y;}
} p[N];int pn;int g[N][N];
int dp[N][(1<<13) + 5];int dis(Point a, Point b) {return abs(a.x - b.x) + abs(a.y - b.y);
}const int INF = 0x3f3f3f3f;
int main() {while (~scanf("%d%d", &n, &m)) {pn = 0;int a;int flag = 0;int zero;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {scanf("%d", &a);if (a) {p[pn++] = Point(i, j);if (i == 0 && j == 0) {flag = 1;zero = pn - 1;}}}}if (!flag) {zero = pn;p[pn++] = Point(0, 0);}for (int i = 0; i < pn; i++) {for (int j = i; j < pn; j++) {g[i][j] = g[j][i] = dis(p[i], p[j]);}}for (int i = 0; i < pn; i++)for (int j = 0; j < (1<<pn); j++)dp[i][j] = INF;dp[zero][0] = 0;dp[zero][(1<<zero)] = 0;int ss = (1<<pn);for (int i = 0; i < ss; i++) {for (int j = 0; j < pn; j++) {if (i&(1<<j)) {for (int k = 0; k < pn; k++) {if (i&(1<<k)) {dp[j][i] = min(dp[j][i], dp[k][i^(1<<j)] + g[j][k]);}}}}}int ans = INF;for (int i = 0; i < pn; i++)ans = min(ans, dp[i][(1<<pn) - 1] + g[zero][i]);printf("%d\n", ans);}return 0;
}

这篇关于HDU 5067 Harry And Dig Machine（状压dp）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---