2050.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2050 on 2006-07-10 at 13:01:24 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 1024;
const int S = 3, A[] = { 2, 2, 1 }, K[] = { 2, 1, 1 };
const int INF = 1 << 28;

int disperse(int*, int);

int main()
{
	int n, m, p[N][2], area[N][S], best[N];
	int i, j, k, x[N], g[N];
	
	while(scanf("%d %d %*d", &n, &m) != EOF) {
		for(i = 0; i < n; i++) {
			scanf("%d %d", &p[i][0], &p[i][1]);
			x[i] = p[i][1];
		}
		int xn = disperse(x, n);
		memset(g, 0, sizeof(g));
		for(i = 0; i < n; i++) {
			int po = lower_bound(x, x+xn, p[i][1])-x;
			g[po] |= 1 << (p[i][0]-1);
		}
		for(i = 0; i <= m; i++) {
			best[i] = INF;
			for(j = 0; j < S; j++) area[i][j] = INF;
		}
		for(i = 0; i < S; i++) {
			if(g[0] == 3 && i == 2) continue;
			area[K[i]][i] = A[i]; 
			best[K[i]] = min(best[K[i]], A[i]);
		}
		for(i = 1; i < xn; i++)
			for(j = m; j > 0; j--) {
				if(g[i] != 3) {
					if(g[i] != g[i-1]) area[j][2] = INF;
					else area[j][2] += x[i]-x[i-1];
					area[j][2] = min(area[j][2], min(best[j-1]+1, area[j][0]+x[i]-x[i-1]));
				} else area[j][2] = INF;
				area[j][1] = min(area[j][1]+2*(x[i]-x[i-1]), best[j-1]+2);
				area[j][0] += 2*(x[i]-x[i-1]);
				if(j >= K[0]) area[j][0] = min(area[j][0], best[j-2]+2);
				area[j][0] = min(area[j][0], area[j-1][2]+x[i]-x[i-1]+1);
				best[j] = INF;
				for(k = 0; k < S; k++) best[j] = min(best[j], area[j][k]);
			}
		printf("%d\n", best[m]);
	}
	
	return 0;
}

int disperse(int* s, int n)
{
	int i, sn = 1;
	sort(s, s+n);
	for(i = 1; i < n; i++)
		if(s[i] != s[i-1]) s[sn++] = s[i];
	return sn;
}