1971.cpp

HDOJ acm.hdu.edu.cn 第10卷的一些题目

//1971
#include <cstdio>
#include <string>
#include <cmath>
#include <queue>
#include <algorithm>
#include <functional>
using namespace std;
const int NMAX = 70;
const int HMAX = 300;
const int TMAX = 30;
// /3的原因是用贪心做剪枝
const int INF = NMAX*TMAX/3 +100;
struct BOOK {
	int h,t;
	bool operator < (const BOOK & bt) const {
		if (h != bt.h) return h > bt.h;
		return t < bt.t;
	}
}book[NMAX];
int n,ans;
int tsum[NMAX];
struct SHELF {
	int h1,h2;
}dp[INF][INF];
void process() {
	int i,j,k;
	for (i=1;i<n;i++) {
		//注意dp方向,略过已更新的值
		for (j=tsum[i-1];j>=0;j--) for (k=tsum[i-1]-j;k>=0;k--) {
			if (j >= INF || k >= INF) continue;
			if (dp[j][k].h1==INF && dp[j][k].h2==INF && !(k==0 && j==tsum[i-1])) continue;
			//first shelf
			if (j+book[i].t < INF && dp[j+book[i].t][k].h1+dp[j+book[i].t][k].h2 > dp[j][k].h1+dp[j][k].h2) {
				dp[j+book[i].t][k].h1 = dp[j][k].h1;
				dp[j+book[i].t][k].h2 = dp[j][k].h2;
			}
			//second shelf
			if (dp[j][k].h1 == INF) dp[j][k].h1 = book[i].h;
			if (k+book[i].t < INF && dp[j][k+book[i].t].h1+dp[j][k+book[i].t].h2 > dp[j][k].h1+dp[j][k].h2) {
				dp[j][k+book[i].t].h1 = dp[j][k].h1;
				dp[j][k+book[i].t].h2 = dp[j][k].h2;
			}
			//third shelf
			if (dp[j][k].h2 == INF) dp[j][k].h2 = book[i].h;
		}
	}
}
int cal() {
	int i,j,k,h,w,ret = INT_MAX;
	for (i=0;i<=tsum[n-1];i++) for (j=0;j<=tsum[n-1]-i;j++) {
		if (j >= INF || i >= INF) continue;
		if (tsum[n-1]-i-j <= 0) continue;
		if (dp[i][j].h1 == INF || dp[i][j].h2 == INF) continue;
		w = max(i,max(j,tsum[n-1]-i-j));
		h = book[0].h + dp[i][j].h1 + dp[i][j].h2;
		ret = min(ret,w*h);
	}
	return ret;
}
int main() {
	int i,j,cas;
	scanf("%d",&cas);
	while (cas --) {
		scanf("%d",&n);
		for (i=0;i<n;i++) scanf("%d %d",&book[i].h,&book[i].t);
		sort(book,book+n);
		tsum[0] = book[0].t;
		for (i=1;i<n;i++) tsum[i] = tsum[i-1] + book[i].t;
		for (i=0;i<INF;i++) for (j=0;j<INF;j++) 
			dp[i][j].h1 = dp[i][j].h2 = INF;
		process();
		printf("%d\n",cal());
	}
}