1901.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1901 on 2006-07-01 at 12:44:25 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int V = 200;
const int SN = 128;
const int INF = 1 << 28;

int main()
{
	int d, cost[V+1], i, j;
	bool end = false;

	while(!end && scanf("%d%*c", &d) != EOF) {
		for(i = 0; i <= V; i++) cost[i] = INF;
		int last = cost[V/2] = 0;
		while(true) {
			char line[64];
			if(gets(line) == NULL) { end = true; break; }
			else if(line[0] == 0) break;
			int sd, v, nxt[V+1]; sscanf(line, "%d %d", &sd, &v);
			if(sd > d) continue;
			sd -= last;
			for(i = 0; i <= V; i++) nxt[i] = INF;
			for(i = V; i >= 0; i--)
				for(j = sd; j <= i+sd && j <= V; j++)
					nxt[i] = min(nxt[i], cost[j]+v*(i-j+sd));
			last += sd; memcpy(cost, nxt, sizeof(cost));
		}
		int best = INF;
		for(i = V/2+d-last; i <= V; i++) best = min(best, cost[i]);
		if(best == INF) printf("Impossible\n");
		else printf("%d\n", best);
	}
	
	return 0;
}