uestc oj 1218 Pick The Sticks (01背包变形)-白红宇

uestc oj 1218 Pick The Sticks (01背包变形)

阅读量：5157 次

发布时间：2019-06-13

本文共 1464 字，大约阅读时间需要 4 分钟。

题目链接：

给出n根木棒的长度和价值，最多可以装在一个长 l 的容器中，相邻木棒之间不允许重叠，且两边上的木棒，可以伸一半的长度在容器外，求最大价值量

01背包是取和不取。那这里我们可以把容器长度 l x 2，筷子长度 x 2，就变成了最多两个筷子取一次(伸一半在外面)，其余的要么取两次，要么不取。

普通01背包，一维dp[i]表示消耗体积i所得到的最大的价值。

那么这里dp[i][k]表示消耗体积i并有k(k <= 2)个在外面所得到的最大的价值。

1     //#pragma comment(linker, "/STACK:102400000, 102400000") 2     #include 
     
       3     #include 
      
        4     #include 
       
         5     #include 
        
          6     #include 
         
           7     #include 
          
            8 #include 
           
             9 #include 
            
             10 #include 
             
              11 #include 
              
               12 #include 
               13 using namespace std;14 typedef long long LL;15 typedef pair 
                
                  P;16 const int N = 4e3 + 5;17 LL dp[N][5]; //dp[i][k]表示使用i体积有k个木板在露在外面的最大价值18 int w[N];19 LL v[N];20 21 int main()22 {23 int t, n, g;24 scanf("%d", &t);25 for(int ca = 1; ca <= t; ++ca) {26 scanf("%d %d", &n, &g);27 LL ans = 0;28 for(int i = 1; i <= n; ++i) {29 scanf("%d %lld", w + i, v + i);30 w[i] <<= 1;31 ans = max(ans, v[i]);32 }33 g <<= 1;34 memset(dp, 0, sizeof(dp));35 for(int i = 1; i <= n; ++i) {36 for(int j = g; j >= w[i]/2; --j) { //一维背包类似，说明下面只能取一次37 for(int k = 0; k <= 2; ++k) {38 if(w[i] <= j) //全放在里面39 dp[j][k] = max(dp[j - w[i]][k] + v[i], dp[j][k]);40 if(k >= 1) //有一半在外面41 dp[j][k] = max(dp[j - w[i]/2][k - 1] + v[i], dp[j][k]);42 }43 }44 }45 for(int i = 0; i <= 2; ++i) {46 ans = max(ans, dp[g][i]);47 }48 printf("Case #%d: %lld\n", ca, ans);49 }50 return 0;51 }

转载于:https://www.cnblogs.com/Recoder/p/5901730.html

你可能感兴趣的文章