1893.cpp

来自「哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码」· C++ 代码 · 共 35 行

/*  This Code is Submitted by wywcgs for Problem 1893 on 2006-03-05 at 02:21:40 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 1024;
const int INF = - 1 << 30;

int main()
{
	int king[MAX], tj[MAX], n;
	int best[MAX], i, j;
	
	while(scanf("%d", &n) != EOF && n != 0) {
		for(i = 0; i < n; i++) scanf("%d", &tj[i]);
		for(i = 0; i < n; i++) scanf("%d", &king[i]);
		sort(king, king+n); sort(tj, tj+n);
		for(best[0] = 0, i = 1; i <= n; i++) best[i] = best[i-1] - 200;
		for(i = 0; i < n; i++) {
			int temp[MAX];
			for(j = 0; j <= n; j++) temp[j] = INF;
			for(j = 0; j <= i; j++) {
				if(king[n-1-j] > tj[i]) temp[j+1] = best[j]-200;
				if(tj[i] >= king[i-j]) temp[j] = max(temp[j], best[j]+(king[i-j] == tj[i] ? 0 : 200));
			}
			memcpy(best, temp, sizeof(temp));
		}
		int win = INF;
		for(i = 0; i <= n; i++) win = max(best[i], win);
		printf("%d\n", win);
	}
	
	return 0;
}