zoj 3471 Most Powerful（状压dp+Tsp问题+连续性问题）

上来直接一波敲键盘，直接套Tsp问题的代码

然后WA

发现貌似这道题没有连续性。

Tsp问题是一条路径，一个点到另一个点，多了一个限制，所以就需要加多一维

而这道题没有限制，也就是说那一维不需要加，我加了还WA

然后要搞清楚状态，在纸上可以写，写清楚了再敲代码

这道题一开始都是存在，初始状态是0000……所以就用0表示存在，1表示不存在

#include<cstdio>

#include<cstring>

#include<algorithm>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

#define _for(i, a, b) for(int i = (a); i <= (b); i++)

using namespace std;

const int MAXN = 15;

int g[MAXN][MAXN], dp[1050], n;

int main()

{

	while(~scanf("%d", &n) && n)

	{

		REP(i, 0, n)

			REP(j, 0, n)

				scanf("%d", &g[i][j]);

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

		REP(S, 0, 1 << n) //i碰j

			REP(i, 0, n) if(!(S & (1 << i))) //还存在是0

				REP(j, 0, n) if(S & (1 << j)) //消失是1

					dp[S] = max(dp[S], dp[S^(1<<j)] + g[i][j]);

		int ans = 0, t = (1 << n) - 1;

		REP(i, 0, n)

			ans = max(ans, dp[t ^ (1 << i)]);

		printf("%d\n", ans);

	}

	return 0;

}

巴特西

zoj 3471 Most Powerful（状压dp+Tsp问题+连续性问题）

最新文章

热门文章