UVA 11766 - Racing Car Computer（DP）

题目链接：11766 - Racing Car Computer

题意：n个人进行比赛，以下n行输入对于每个人而言，有a个人在他前面，b个人在他后面。可能并排，问根据所有人情况，找出矛盾最小的数目。

思路：这题只要想通一点就很简单了。

对于每个人而言，他的位置可能的区间为[a + 1, n - b]。

那么对于两个人而言，如果他们可能区间相交，那么肯定矛盾，反之则不矛盾。

证明：如果区间[l1, r1]和[l2, r2]相交，说明l2 >= r2。第2个人前面有l2 - 1个人，L2 - 1 < r1，所以如果这样算总人数肯定会超过n个人，这个在纸上多画几个就能看出来了。

那么我们只要统计每个区间有多少人，（注意每个区间[l, r]的人数最多为r - l + 1），然后dp[i]为1-i排名的最多共存情况（求出最多共存等于求出最小不矛盾），那么状态转移方程就出来了为：

dp[i] = min{dp[j] + w[j + 1][i]}， 时间复杂度为O(n^2)。

代码：

#include <stdio.h>
#include <string.h>
#define max(a,b) ((a)>(b)?(a):(b))
const int N = 1005;
int n, a, b, w[N][N], dp[N];

int solve() {
	for (int i = 1; i <= n; i++) {
		dp[i] = 0;
		for (int j = 0; j < i; j++)
			dp[i] = max(dp[i], dp[j] + w[j + 1][i]);
	}
	return dp[n];
}

int main() {
	int cas = 0;
	while (~scanf("%d", &n) && n) {
		memset(w, 0, sizeof(w));
		for (int i = 0; i < n; i++) {
			scanf("%d%d", &a, &b);
			if (a + b >= n) continue;
			if (w[a + 1][n - b] == n - b - a) continue;
			w[a + 1][n - b]++;
		}
		printf("Case %d: %d\n", ++cas, n - solve());
	}
	return 0;
}

UVA 11766 - Racing Car Computer（DP）,布布扣,bubuko.com

UVA 11766 - Racing Car Computer（DP）

原文：http://blog.csdn.net/accelerator_/article/details/22172491