2198.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2198 on 2006-04-10 at 20:17:22 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int VM = 1024;
const int INF = 1 << 30;

int main()
{
	int cost[VM], w, b, ex, lmt;
	int i, j, k;

	while(scanf("%d", &w) != EOF && w != 0) {
		scanf("%d %d %d", &b, &ex, &lmt);
		for(i = 0; i <= lmt; i++) cost[i] = INF;
		cost[0] = 0;
		for(i = 0; i < w; i++) {
			int r, c, nct[VM]; scanf("%d %d", &c, &r);
			for(j = 0; j <= lmt; j++) {
				nct[j] = INF;
				for(k = 0; k <= lmt; k++) {
					if(k-j > r) break;
					int cc = cost[k]+ex*k, need = r+j-k;
					if(need > 0) cc += b+need*c;
					nct[j] = min(nct[j], cc);
				}
			}
			memcpy(cost, nct, sizeof(cost));
		}
		printf("%d\n", cost[0]);
	}
	
	return 0;
}