Andrew Stankevich’s Contest #3解题报告 » ZOJ2366

ZOJ2366
ZOJ2366.cpp


#include <map>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int main() {
	int re, z, na, nb;
	char c[256], sa[4004], sb[4004];
	map<char, int> alphabet;
	int dist[256][256];
	int mina[256], minb[256];
	int a[2002], b[2002];
	static int dp[2002][2002], pre[2002][2002];

	scanf("%d", &re);
	for (int ri = 1; ri <= re; ++ri) {
		if (ri > 1) {
			putchar('\n');
		}
		scanf("%s", c);
		// gets(c);
		z = strlen(c);
		alphabet.clear();
		for (int i = 0; i < z; ++i) {
			alphabet1] = i;
			mina[i] = minb[i] = 0;
		}
		scanf("%s", sa);
		// gets(sa);
		na = strlen(sa);
		for (int i = 0; i < na; ++i) {
			a[i] = alphabet[sa[i]];
		}
		scanf("%s", sb);
		// gets(sb);
		nb = strlen(sb);
		for (int i = 0; i < nb; ++i) {
			b[i] = alphabet[sb[i]];
		}
		for (int i = 0; i < z; ++i) {
			for (int j = 0; j < z; ++j) {
				scanf("%d", &dist[i][j]);
				if (dist[i][j] < dist[i][mina[i]]) {
					mina[i] = j;
				}
				if (dist[i][j] < dist[minb[j]][j]) {
					minb[j] = i;
				}
			}
		}

		dp[0][0] = 0;
		pre[0][0] = -1;
		for (int i = 0; i < na; ++i) {
			dp[i + 1][0] = dp[i][0] + dist[a[i]][mina[a[i]]];
			pre[i + 1][0] = 0;
		}
		for (int j = 0; j < nb; ++j) {
			dp[0][j + 1] = dp[0][j] + dist[minb[b[j]]][b[j]];
			pre[0][j + 1] = 1;
		}
		for (int i = 0; i < na; ++i) {
			for (int j = 0; j < nb; ++j) {
				if (dp[i][j + 1] + dist[a[i]][mina[a[i]]] < dp[i + 1][j] + dist[minb[b[j]]][b[j]]) {
					dp[i + 1][j + 1] = dp[i][j + 1] + dist[a[i]][mina[a[i]]];
					pre[i + 1][j + 1] = 0;
				} else {
					dp[i + 1][j + 1] = dp[i + 1][j] + dist[minb[b[j]]][b[j]];
					pre[i + 1][j + 1] = 1;
				}
				if (dp[i][j] + dist[a[i]][b[j]] < dp[i + 1][j + 1]) {
					dp[i + 1][j + 1] = dp[i][j] + dist[a[i]][b[j]];
					pre[i + 1][j + 1] = 2;
				}
			}
		}
		printf("%d\n", dp[na][nb]);
		z = 0;
		while (pre[na][nb] != -1) {
			switch (pre[na][nb]) {
				case 0:
					--na;
					sa[z] = c[a[na]];
					sb[z] = c[mina[a[na]]];
					break;
				case 1:
					--nb;
					sa[z] = c[minb[b[nb]]];
					sb[z] = c[b[nb]];
					break;
				case 2:
					--na;
					--nb;
					sa[z] = c[a[na]];
					sb[z] = c[b[nb]];
					break;
			}
			++z;
		}
		reverse(sa, sa + z);
		reverse(sb, sb + z);
		sa[z] = sb[z] = '\0';
		puts(sa);
		puts(sb);
	}

	return 0;
}
//Run ID  	Submit Time  	Judge Status  	Problem ID  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name
//1806156 	2009-03-27 08:26:36 	Accepted 	2366 	C++ 	260 	31488 	watashi@Zodiac
Leave a Reply