[题解]ZOJ Monthly, February 2011 » ZOJ3471

ZOJ3471
ZOJ3471.cpp


#include <cstdio>
#include <algorithm>
using namespace std;

const int bin[11] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024};
int mp[10][10];
int dp[1024];

int main(void)
{
	int n;

	while(scanf("%d", &n) != EOF && n > 0) {
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				scanf("%d", &mp[i][j]);
		fill(dp, dp + bin[n], 0);
		for (int k = 0; k < bin[n]; k++) {
			for (int i = 0; i < n; i++) {
				if(k & bin[i])
					continue;;
				for (int j = 0; j < n; j++) {
					if(k & bin[j])
						continue;
					if(i == j)
						continue;
					dp[k | bin[j]] = max(dp[k | bin[j]], dp[k] + mp[i][j]);
				}
			}
		}
		printf("%d\n", *max_element(dp, dp + bin[n]));
	}

	return 0;
}

//Run ID 	Submit Time 	Judge Status 	Problem ID 	Language 	Run Time(ms) 	Run Memory(KB) 	User Name 	Admin
//707 	2011-02-08 20:30:59 	Accepted 	E 	C++ 	60 	184 	watashi@ArcOfDream 	Source
7 Responses to “ZOJ3471”
  1. lw says:

    这题标称有问题
    比如这组数据
    3
    0 3 100
    5 0 0
    0 0 0
    按题目意思应该是103
    但是答案是105

  2. iantll says:

    mask dp ? 状态压缩 dp?

  3. lengxiang says:

    应该是这样理解,在k中的i去撞不在k中的j…

    反正数据各种强大,保证大家能AC…

  4. lengxiang says:

    这个地方貌似有错。
    if(k & bin[i])

    应该是if(!(k&bin[i]))continue;

    我交了下,不改60MS过,改了50MS过

    • watashi says:

      应该是if (k & bin[i]) continue;吧
      表示k中i和j都还没有消失,然后j消失了?
      囧,看来数据比较弱
      这是summer2008的题,因为有不少人验过了,所以也没怎么在意

  5.  
Leave a Reply