1755.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1755 on 2006-03-12 at 12:29:59 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 320;
const int N_MAX = 32;
const int INF = 1 << 30;

class Site {
public:
	int n, a[N_MAX], b[N_MAX];
	void make();
	int chose(int) const;
};
void Site::make() {
	scanf("%d", &n); int i;
	a[0] = b[0] = 0;
	for(i = 1; i <= n; i++) scanf("%d", &a[i]);
	for(i = 1; i <= n; i++) scanf("%d", &b[i]);
}
int Site::chose(int x) const {
	return a[x]+b[n-x];
}

int main()
{
	int t1, t2, n, cost[MAX];
	Site site[N_MAX];
	int i, j, k;
	
	while(scanf("%d %d", &t1, &t2) != EOF && t1+t2 != 0) {
		for(i = 1; i <= t1; i++) cost[i] = INF;
		scanf("%d", &n);
		for(i = 0; i < n; i++) site[i].make();
		int step = cost[0] = 0;
		for(i = 0; i < n; i++) {
			step += site[i].n;
			for(j = min(step, t1); j >= 0; j--) {
				int nxt = INF;
				for(k = 0; k <= site[i].n && k <= j; k++)
					nxt = min(nxt, cost[j-k]+site[i].chose(k));
				cost[j] = nxt;
			}
		}
		printf("%d\n", cost[t1]);
	}
	
	return 0;
}