[题解]ZOJ Monthly, May 2011 » ZOJ3502

ZOJ3502
ZOJ3502.cpp


#include <cstdio>
#include <string>
#include <utility>
#include <algorithm>

using namespace std;

const double EPS = 1e-8;
const int MAXN = 12;

double p[MAXN][MAXN];
double dp[1 << MAXN];
string pre[1 << MAXN];

int main() {
	int re, n;
	double q;

	scanf("%d", &re);
	for (int ri = 1; ri <= re; ++ri) {
		scanf("%d", &n);
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				scanf("%lf", &p[i][j]);
			}
		}
		dp[0] = 0;
		pre[0] = "";
		for (int k = 1; k < (1 << n); ++k) {
			dp[k] = -1;
			for (int i = 0; i < n; ++i) {
				if (k & (1 << i)) {
					q = 0;
					for (int j = 0; j < n; ++j) {
						if (k & (1 << j)) {
							q = max(q, p[j][i]);
						}
					}
					q = dp[k ^ (1 << i)] + q / 100;
					if ((q > dp[k] + EPS) || (q > dp[k] - EPS && pre[k ^ (1 << i)] < pre[k])) {
						dp[k] = q;
						pre[k] = pre[k ^ (1 << i)];
						pre[k] += ('A' + i);
					}
				}
			}
		}
		printf("%.2f\n%s\n", dp[(1 << n) - 1], pre[(1 << n) - 1].c_str());
	}

	return 0;
}

//Run ID 	Submit Time 	Judge Status 	Problem ID 	Language 	Run Time(ms) 	Run Memory(KB) 	User Name 	Admin
//740 	2011-04-27 03:24:50 	Accepted 	C 	C++ 	40 	228 	watashi@ArcOfDream 	Source
Leave a Reply