POJ 3124 The Bookcase——dp

POJ 3124 The Bookcase——dp

很好的一道背包题，思路这篇博客写的很好​

然而写完了发现居然2900s！！！，卡边过对于强迫症来说是致命的，不过也好优化，在上面思路的基础上记录维护一下宽度的前缀和，dp时和宽度极限值做一个min就好了，成功优化到1500s

#include #include #include #include using namespace std;const int maxn = 1500;const int INF = 0x3f3f3f3f;int T, n;struct Node { int h, w; bool operator < (const Node &t) const { return h > t.h; }}node[100];int dp[maxn][maxn], sum[maxn];int main() { scanf("%d", &T); while (T--) { scanf("%d", &n); int maxh = 0, sumw = 0; for (int i = 1; i <= n; i++) { scanf("%d %d", &node[i].h, &node[i].w); maxh = max(maxh, node[i].h); sumw += node[i].w; } sort(node+1, node+1+n); sum[0] = 0; for (int i = 1; i <= n; i++) sum[i] = sum[i-1] + node[i].w; int len = sumw / 2; for (int i = 0; i <= len; i++) { for (int j = 0; j <= len; j++) { dp[i][j] = INF; } } dp[0][0] = maxh; for (int k = 2; k <= n; k++) { for (int i = min(sum[k], len); i >= 0; i--) { for (int j = min(sum[k] - i, len); j >= 0; j--) { if (i-node[k].w > 0) dp[i][j] = min(dp[i][j], dp[i-node[k].w][j]); if (i-node[k].w==0) dp[i][j] = min(dp[i][j], dp[i-node[k].w][j]+node[k].h); if (j-node[k].w > 0) dp[i][j] = min(dp[i][j], dp[i][j-node[k].w]); if (j-node[k].w==0) dp[i][j] = min(dp[i][j], dp[i][j-node[k].w]+node[k].h); } } } int ans = INF; for (int i = 0; i <= len; i++) { for (int j = 0; j <= len; j++) { if (!i || !j || i + j >= sumw || dp[i][j] == INF) continue; ans = min(ans, dp[i][j]*max(sumw-i-j,max(i,j))); } } printf("%d\n", ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。