[HDOJ5543]Pick The Sticks（DP，01背包）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5543

题意：往长为L的线段上覆盖线段，要求：要么这些线段都在L的线段上，要么有不超过自身长度一半的部分在线段外面，最多有两条这样的线段（在两头）。

dp(i,j,k)表示前i个线段覆盖在长度为j的线段上，期中有k个线段不完全在这个线段上的最大价值。考虑线段长度的奇偶问题，所以事先把L和其他线段长度乘2，以便操作。所以枚举所有线段，一般情况，就是01背包的问题，dp(i,j,k)=max(dp(i,j,k), dp(i-1,j-w(i),k)+v(i))。当枚举到k不是0的时候，还需要更新两端放的情况：dp(i,j,k)=max(dp(i,j,k),dp(i-1,j-w(i)/2,k-1)+v(i))。直接取w(i)/2是没有关系的，因为我们在这里希望可以贪心地尽可能地少占用当前L上的长度。

还有一个trick：L=1的时候这么搞。这时L当成一个支点，只能放一个。所以要提前处理所有线段的最大价值。

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 const int maxn = ;

 int w[maxn], v[maxn];

 int n, L;

 LL dp[maxn][];

 LL ret;

 int main() {

   freopen("in", "r", stdin);

   int T, _ = ;

   scanf("%d", &T);

   while(T--) {

     scanf("%d %d", &n, &L);

     memset(dp, , sizeof(dp));

     ret = ; L <<= ;

     for(int i = ; i <= n; i++) {

       scanf("%d %d", &w[i], &v[i]);

       w[i] <<= ;

       ret = max(ret, (LL)v[i]);

     }

     for(int i = ; i <= n; i++) {

       for(int j = L; j >= w[i]/; j--) {

         for(int k = ; k <= ; k++) {

           if(j >= w[i]) dp[j][k] = max(dp[j][k], dp[j-w[i]][k]+v[i]);

           if(k) dp[j][k] = max(dp[j][k], dp[j-w[i]/][k-]+v[i]);

            ret = max(ret, dp[j][k]);

         }

       }

     }

     printf("Case #%d: %lld\n", _++, ret);

   }

   return ;

 }

巴特西

[HDOJ5543]Pick The Sticks（DP，01背包）

最新文章

热门文章