2339.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2339 on 2006-08-25 at 17:05:23 */ 
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 5;
const int PN = 512;
const int INF = 1 << 30;

vector<int> prc[N];
int m, f, c, r, cost;
int u[N], tu[N+1] = { 0 };

void assign(int, int, int);
bool canLive();
int maxLive(int);

int main()
{
	int T;
	
	scanf("%d", &T);
	for(int t = 0; t < T; t++) {
		scanf("%d %d %d %d", &m, &f, &r, &c);
		for(int i = 0; i < N; i++) prc[i].clear();
		for(int i = 0; i < r; i++) {
			int b, p; scanf("%d %d", &b, &p);
			prc[b-1].push_back(p);
		}
		if(m > f) swap(m, f);
		for(int i = 0; i < N; i++) sort(prc[i].begin(), prc[i].end());
		for(int i = 1; i <= N; i++) tu[i] = tu[i-1]+i*prc[i-1].size();
		cost = INF; assign(4, 0, 0);
		if(cost == INF) printf("Impossible\n");
		else printf("%d\n", cost);
	}
	
	return 0;
}

void assign(int d, int cc, int tsp)
{
	if(tu[d+1]+tsp < m+f) return;
	for(u[d] = 0; u[d] <= prc[d].size(); u[d]++) {
		if(u[d] != 0) {
			if(d != N-1 && u[d+1] != prc[d+1].size() && prc[d][u[d]-1] >= prc[d+1][u[d+1]]) break;
			cc += prc[d][u[d]-1]; tsp += d+1;
		}
		if(cc >= cost) break;
		else if(tsp >= m+f && canLive()) { cost = cc; break; }
		if(d != 0) assign(d-1, cc, tsp);
	}
	u[d] = 0;
}
bool canLive()
{
	if(maxLive(m) >= f) return true;
	else if(c != 0) {
		for(int i = 1; i < N; i++) {
			if(u[i] == 0) continue;
			u[i]--; int mf = maxLive(m-1); u[i]++;
			return mf >= f-1;
		}
	}
	return false;
}
int maxLive(int n)
{
	int rn[PN] = { 0 };
	for(int i = 1; i < PN; i++) rn[i] = -INF;
	for(int i = 0; i < 5; i++) {
		for(int j = 0; j < u[i]; j++) {
			for(int k = n; k >= 0; k--) {
				rn[k] = max(rn[k]+i+1, rn[max(k-i-1, 0)]);
			}
		}
	}
	return rn[n];
}