脚本宝典收集整理的这篇文章主要介绍了POJ3124.The Bookcase(题解),脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
思路:我们发现一共需要求两维东西,一个是宽度,另一个是高度,那么依据我们的经验,可以将高度首先进行一次排序。那么是由高到低排好,还是由低到高排好呢?
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define ch() getchar()
#define pc(x) putchar(x)
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define bep(i, a, b) for (int i = a; i >= b; --i)
#define lowbit(x) x &(-x)
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define PI acos(-1)
using namespace std;
template <typename T>
void read(T &x) {
static char c;
static int f;
for (c = ch(), f = 1; c < '0' || c > '9'; c = ch())
if (c == '-') f = -f;
for (x = 0; c >= '0' && c <= '9'; c = ch()) x = x * 10 + (c & 15);
x *= f;
}
template <typename T>
void write(T x) {
static char q[65];
int cnt = 0;
if (x < 0) pc('-'), x = -x;
q[++cnt] = x % 10, x /= 10;
while (x) q[++cnt] = x % 10, x /= 10;
while (cnt) pc(q[cnt--] + '0');
}
const int N = 2130;
int _, n;
int f[N][N];
struct node {
int h, t;
bool operator<(const node &a) const { return a.h < h; }
} a[N];
void solve() {
read(_); // memset(f,0x3f,sizeof f);
while (_--) {
read(n);
int sum = 0;
// memset(f, 0x3f, sizeof f);
int sums = 0;
f[0][0] = 0;
rep(i, 1, n) {
int x, y;
read(x);
read(y);
sums += y;
a[i].h = x;
a[i].t = y;
}
memset(f,0x3f,sizeof f);
f[0][0] = 0;
sort(a + 1, a + 1 + n);
int ans = 99999999;
rep(i, 2, n) { // printf("%dn",a[i].h);
//sum += a[i].t;
bep(j, sums, 0) {
for (int k = sums; k >= 0; --k) {
//int &res = f[j][k];
if(f[j][k] == 0x3f3f3f3f or j+k > sums)continue;
f[j + a[i].t][k] = min(f[j + a[i].t][k],
f[j][k] + (j == 0 ? a[i].h : 0));
f[j][k + a[i].t] = min(
f[j][k + a[i].t], f[j][k] + (k == 0 ? a[i].h : 0));
//res = 0x3f3f3f3f;
// if (j - a[i].t >= 0)
// res = min(
// res, f[j - a[i].t][k] + (j == a[i].t ? a[i].h : 0));
// if (k - a[i].t >= 0)
// res = min(
// res, f[j][k - a[i].t] + (k == a[i].t ? a[i].h : 0));
// res = min(res,
// f[j][k] + (sum - (j + k) == a[i].t ? a[i].h : 0));
}
}
sum += a[i].t;
}
rep(i, 1, sums) {
rep(j, 1, sums) {
if (f[i][j] >= 0x3f3f3f3f or i + j >= sums) continue;
// printf("{%d %d %d} %d %d %dn",i,j,sum-i-j,f[n][i][j],
// max({i,j,sum-i-j}),f[n][i][j] * max({i,j,sum-i-j}));
ans = min((f[i][j] + a[1].h) * max(max(i, j), sums - i - j), ans);
// f[0][i][j] = f[1][i][j] = 0x3f3f3f3f;
}
}
write(ans);
pc('n');
}
}
signed main(int argc, char const *argv[]) {
solve();
return 0;
}
以上是脚本宝典为你收集整理的POJ3124.The Bookcase(题解)全部内容,希望文章能够帮你解决POJ3124.The Bookcase(题解)所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。