書上，作者分析很詳細(xì)?

#include<iostream> #include<algorithm> #include<math.h> #include<string.h> #include<stdio.h> #include<string> #include<vector> #include<queue> #include<map> #include<sstream> #include<cassert> using namespace std; const int maxn = 70 + 5; const int maxw = 30; const int INF = 1000000000; struct Book {int h, w;bool operator<(const Book& rhs) {return h > rhs.h || (h == rhs.h&&w > rhs.w);} }book[maxn];int d[2][maxn*maxw][maxn*maxw]; int sumw[maxn]; inline int f(int w, int h) {return w == 0 ? h : 0; } inline void update(int &newd, int d) {if (newd < 0 || d < newd)newd = d; } int main() {int T;cin >> T;while (T--) {int n;cin >> n;for (int i = 0; i < n; i++) {cin >> book[i].h >> book[i].w;}sort(book, book + n);sumw[0] = 0;for (int i = 1; i <= n; i++) {sumw[i] = sumw[i - 1] + book[i - 1].w;}d[0][0][0] = 0;int t = 0;for (int i = 0; i < n; i++) {for (int j = 0; j <= sumw[i + 1]; j++) {for (int k = 0; k < sumw[i + 1] - j; k++)d[t ^ 1][j][k] = -1;}for (int j = 0; j <=sumw[i]; j++) {for (int k = 0; k <= sumw[i] - j; k++)if (d[t][j][k] >= 0) {update(d[t ^ 1][j][k], d[t][j][k]);update(d[t ^ 1][j + book[i].w][k], d[t][j][k] + f(j, book[i].h));update(d[t ^ 1][j][book[i].w], d[t][j][k] + f(k, book[i].h));}}t ^= 1;}int ans = INF;for (int j = 1; j <= sumw[n]; j++) {for (int k = 1; k <= sumw[n] - j; k++)if (d[t][j][k] >= 0) {int w = max(max(j, k), sumw[n] - j - k);int h = book[0].h + d[t][j][k];ans = min(ans, w*h);}}cout << ans << endl;}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的uva12099 Bookcase ACM NWERC的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。