openjudge4979 - 海贼王之伟大航路题解

原题链接

题目简要分析

N个点，从1号点到N号点求最短路径,且每个点都要遍历到。现在要你求出最优方案。

这道题看到后，首先的想法莫过于搜索、暴力了。这显然不太可能。而进一步思考，使用Floyed和Dijkstra也不太好用，因为题目描述说:"每个点都要遍历到"，自然又否决了这个方法。那么怎么办呢？

状态压缩DP

什么是状态压缩？

由于所有点在DP阶段中的状态只有走过( true )和没走过( false )，那么用0、1的二进制表示每个阶段即可。

比如现在有5个点，现在只经过了2、3、5号点。那么二进制就可以这样表示：

再转换成十进制即可

如何记录阶段？

所以我们的DP数组需要二维，一维记录当前二进制状态用十进制表示的数，另一维记录当前阶段点，也就是当前点是否经过。

dp[i][j] 表示i状态下走到j号点最优方案

状态转移方程是什么？

我们只要再枚举一个点，即枚举上一个点，合法就取min值即可。

AC代码

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 20 + 5;

int n,dp[(1 << 17)][MAXN];

int dis[MAXN][MAXN];

inline int read(){//快速读入

    int f = 1, x = 0;

    char c = getchar();

    while (c < '0' || c > '9')

    {

        if (c == '-')

            f = -1;

        c = getchar();

    }

    while (c >= '0' && c <= '9')

    {

        x = x * 10 + c - '0';

        c = getchar();

    }

    return f * x;

}

int Hamilton(){

	memset(dp,0x3f,sizeof(dp));

	dp[1][1] = 0;

	for(int i = 1;i <= (1 << (n + 1)) - 1; i++){

		for(int j = 1;j <= n; j++){

			if(!((i >> j) & 1))continue;

			for(int k = 1;k <= n; k++){

				if(!((i >> k) & 1))continue;

				dp[i][j] = min(dp[i][j],dp[i ^ (1 << j)][k] + dis[k][j]);

			}

		}

	}

	return dp[(1 << (n + 1)) - 1][n];

}

int main(){

	n = read();

	for(int i = 1;i <= n; i++)

		for(int j = 1;j <= n; j++){

			dis[i][j] = read();

		}

	//dp[i][j]:i表示所有点压缩后的状态,j表示当前在的点

	//则dp[(1 << (n + 1)) - 1][n]就是最后答案

	cout<<Hamilton();

	return 0;

}

巴特西

openjudge4979 - 海贼王之伟大航路题解

题目简要分析

状态压缩DP

AC代码

最新文章

热门文章

巴特西

openjudge4979 - 海贼王之伟大航路 题解

题目简要分析

状态压缩DP

AC代码

最新文章

热门文章

openjudge4979 - 海贼王之伟大航路题解