?

題目傳送門

題意：長度為L的金條，將n根金棍盡可能放上去，要求重心在L上，使得價值最大，最多有兩條可以長度折半的放上去。

分析：首先長度可能為奇數，先*2。然后除了兩條特殊的金棍就是01背包，所以dp[now][j][k]表示當前狀態，長度為j，使用了k條特殊金棍獲得的最大價值，需要對內存和時間優化。

?

/************************************************* Author :Running_Time* Created Time :2015/10/21 星期三 11:55:40* File Name :D.cpp************************************************/ #include <bits/stdc++.h> using namespace std;#define lson l, mid, rt << 1 #define rson mid + 1, r, rt << 1 | 1 typedef long long ll; const int N = 1e3 + 10; const int L = 4e3 + 10; const int INF = 0x3f3f3f3f; const int MOD = 1e9 + 7; const double EPS = 1e-8; ll dp[2][L][3]; struct P {int a;ll v; }p[N];ll Max(ll a, ll b) {return a > b ? a : b; }int main(void) {int T, cas = 0; scanf ("%d", &T);while (T--) {int n, l; scanf ("%d%d", &n, &l);l *= 2;ll ans = 0;for (int i=1; i<=n; ++i) {scanf ("%d%lld", &p[i].a, &p[i].v);p[i].a *= 2;ans = max (ans, p[i].v);}memset (dp, 0, sizeof (dp));int now = 1;for (int i=1; i<=n; ++i) {now = 1 - now;for (int j=0; j<=l; ++j) {for (int k=0; k<3; ++k) {dp[now][j][k] = dp[1-now][j][k];}}for (int j=l; j>=p[i].a/2; --j) {for (int k=0; k<3; ++k) {if (j >= p[i].a) dp[now][j][k] = max (dp[now][j][k], dp[1-now][j-p[i].a][k] + p[i].v);if (k) dp[now][j][k] = max (dp[now][j][k], dp[1-now][j-p[i].a/2][k-1] + p[i].v);}}for (int i=0; i<2; ++i) {for (int j=0; j<=l; ++j) {for (int k=0; k<3; ++k) ans = max (ans, dp[i][j][k]);}}}printf ("Case #%d: %lld\n", ++cas, ans);}return 0; }

　　

轉載于:https://www.cnblogs.com/Running-Time/p/4923761.html

總結

以上是生活随笔為你收集整理的DP(01背包) UESTC 1218 Pick The Sticks (15CCPC C)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。