首页 > ACM题库 > HDU-杭电 > HDU 4381-Grid-背包问题-[解题报告]HOJ
2015
05-24

HDU 4381-Grid-背包问题-[解题报告]HOJ

Grid

问题描述 :

  There are n boxes in one line numbered 1 to n, at the beginning, all boxes are black. Two kinds of operations are provided to you:

1 ai xi :You can choose any xi black boxes in interval [1,ai], and color them white;
2 ai xi :You can choose any xi black boxes in interval [ai,n], and color them white;

  lcq wants to know if she use these operations in optimal strategy, the maximum number of white boxes she can get, and if she get maximum white boxes, the minimum number of operations she should use.
Tips:
1. It is obvious that sometimes you can choose not to use some operations.
2. If the interval of one operation didn’t have enough black boxes, you can’t use this operation.

输入:

  The first line contains one integer T, indicating the number of test case.
  The first line of each test case contains two integers N (1 <= N <= 1000) and M (1<=M<=1000), indicating that there are N grids and M operations in total. Then M lines followed, each of which contains three integers si(1<=si<=2) , ai and xi (0 <= xi <= N,1<=ai<=N), si indicating the type of this operation, ai and xi indicating that the interval is [1,ai] or [ai,n](depending on si), and you can choose xi black boxes and color them white.

输出:

  The first line contains one integer T, indicating the number of test case.
  The first line of each test case contains two integers N (1 <= N <= 1000) and M (1<=M<=1000), indicating that there are N grids and M operations in total. Then M lines followed, each of which contains three integers si(1<=si<=2) , ai and xi (0 <= xi <= N,1<=ai<=N), si indicating the type of this operation, ai and xi indicating that the interval is [1,ai] or [ai,n](depending on si), and you can choose xi black boxes and color them white.

样例输入:

1
5 2
2 3 3
1 3 3

样例输出:

Case 1: 3 1

Brief Description:

给定n个块,编号从1到n,以及m个操作,初始时n个块是白色。

操作有2种形式:

1 ai xi : 从[1,ai]选xi个块,将这些块涂白。

2 ai xi:从[ai,n]选xi个块,将这些块涂白。

可以忽略某些操作且如果区间内没有足够的黑块(黑块用于涂白),则不能进行这个操作。

Analysis:

写写画画一看就知道这道题是一个背包问题。

一开始用“不恰好装满背包”方法,后来发现是错的(找到了错误数据)。

应该用更精确的“恰好装满背包”。

以下摘自题解:

本题难点在于正确处理两种操作,不妨假设只有一种操作,那么这种操作如果是1的话那么就把操作按照a从小到大排序,每次都尽量往最左边涂,如果是2的话则类似的涂到最右边,但本题两种操作都出现了。

先考虑第一问:

我们把所有的操作按类别区分开,假设所有的1操作尽量用上能从1涂到a格子,所有的2操作尽量用上能从b格子涂到n,假设a<b,那么答案显然是a+n-b+1。那么假设a>=b,那么假设1操作从1涂到x,那么2操作一定会从n尽量往左边涂,直到x为止。最后两边的总和就是答案。

由上不难想到一个DP,l[i][j]表示用了前i种1操作,从1涂到j的最小操作数,转移l[i][j]=min(l[i][j],l[i-1][j-ope[i].x]+1)(ope[i].x<=j<=ope[i].a),类似的,我们可以得到r[i][j]表示用2操作从j涂到n需要的最小操作数。dp复杂度O(n*m)。(这个背包也可以压缩一维,后面的l,r均为1维的状态)

那么我们倒着枚举涂色最大的数目,假设为k,这个数目必然由1操作贡献一部分,由2操作贡献一部分(也可能一个贡献全部,另一个为0),那么我们枚举1操作涂到了i,那么2操作必然涂到了n-(k-i)+1,如果l[i]和r[n-(k-i)+1]均有值,那么说明这个最大数目是可达的,即是第一问的答案。枚举复杂度O(n*n)。

再考虑第二问:

现在我们已经知道最大数目了,这个数目是由操作1和操作2一起贡献的,那么我们仍然可以枚举操作1涂到了i,那么操作2涂到了n-(ans-i)+1,如果l[i]和r[n-(k-i)+1]均有值,那么其和可以用来更新第二问的答案,最后第二问的答案为所有合法方案需操作数的最小值。枚举复杂度O(n*n)。

代码如下:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
const int maxn = 2005;
struct node{
    int aa,cor;
    node(){}
    node(int _aa,int _cor){
       aa = _aa;   cor = _cor;
    }
}x1[maxn],x2[maxn];
int n,m;
int dp1[maxn],dp2[maxn];
int sumx1,sumx2;

bool cmp(const node &p,const node &q){
    return p.aa < q.aa;
}

int main()
{
    int cas,ta=1;
    scanf("%d",&cas);
    while(cas--){
         int i,j;
         scanf("%d%d",&n,&m);

         sumx1 = sumx2 = 1;
         for(i=0; i<m; i++){
             int key,yy,z;
             scanf("%d%d%d",&key,&yy,&z);
             if(key == 1){
                x1[sumx1++] = node(yy,z);
             }else{
                x2[sumx2++] = node(n+1-yy,z);
             }
         }
         sort(x1+1,x1+sumx1,cmp);
         sort(x2+1,x2+sumx2,cmp);
         memset(dp1,0x3f,sizeof(dp1));
         memset(dp2,0x3f,sizeof(dp2));

         dp1[0] = dp2[0] = 0;
         for(i=1; i<sumx1; i++){
             for(j=x1[i].aa; j>=x1[i].cor; j--){
                dp1[j] = min(dp1[j],dp1[j-x1[i].cor]+1);
             }
         }// for

         for(i=1; i<sumx2; i++){
             for(j=x2[i].aa; j>=x2[i].cor; j--){
                dp2[j] = min(dp2[j],dp2[j-x2[i].cor]+1);
             }
         }// for

         int ans = 0,anssum = 0,tmp;
         for(i=1; i<=n; i++){
            if(i == 3){
              tmp = 1;
            }
            for(j=0; j<=i; j++){
               tmp = dp1[j] + dp2[i-j];
               if(tmp <= m){
                  if(ans != i){
                    ans = i;   anssum = tmp;
                  }else if(tmp < anssum){
                      anssum = tmp;
                  }
               }
            }
         }

         printf("Case %d: %d %d\n",ta++,ans,anssum);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/linweiway67/article/details/7894046