hdu 4381 背包

hdu 4381 背包

 

 

Problem Description 　　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 a_i x_i ：You can choose any x_i black boxes in interval [1,a_i], and color them white;
2 a_i x_i ：You can choose any x_i black boxes in interval [a_i,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.

Input 　　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 s_i(1<=s_i<=2) , a_i and x_i (0 <= x_i <= N,1<=a_i<=N), si indicating the type of this operation, a_i and x_iindicating that the interval is [1,a_i] or [a_i,n](depending on s_i), and you can choose x_i black boxes and color them white.

Output 　　For each test case, output case number first. Then output two integers, the first one is the maximum boxes she can get, the second one is the minimum operations she should use.

Sample Input

1
5 2
2 3 3
1 3 3

Sample Output

Case 1: 3 1

/**
hdu 4381 背包變形
題目大意：給定一個區間1~n，所有n個點都是黑色，操作：1 a b 把1~a區間內的b個點變成白色，2 a b 把a~n之間的b個點變成白色，若給定區間黑點數目
           不足b個，則該操作不能執行，問最多能變成多少白色，若變成最多的白色那麼最少的操作數是多少？
解題思路：我們把1~a操作的區間按a值遞增排序，每次先塗最左邊的，dp[j]表示用塗滿前j個點的最少操作數，狀態轉移方程為：dp1[j]=min(dp1[j],dp1[j-p1[i].num]+1);
           a~n的區間做一個轉換後和1~a一樣操作。然後枚舉塗的個數i即可，dp1[j]+dp2[i-j]<=m,有效。其中i：1~n，j:0~i
*/
#include 
#include 
#include 
#include 
using namespace std;
struct note
{
    int x,num;
    bool operator < (const note &other)const
    {
        return x=p1[i].num; j--)
            {
                dp1[j]=min(dp1[j],dp1[j-p1[i].num]+1);
            }
        }
        for(int i=0; i=p2[i].num; j--)
            {
                dp2[j]=min(dp2[j],dp2[j-p2[i].num]+1);
            }
        }
        int tmp,ans=0,sum=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=i;j++)
            {
                tmp=dp1[j]+dp2[i-j];
                if(tmp<=m)
                {
                    if(ans!=i)
                    {
                        ans=i;
                        sum=tmp;
                    }
                    else
                    {
                        sum=min(sum,tmp);
                    }
                }
            }
        }
        printf(Case %d: %d %d
,++tt,ans,sum);
    }
    return 0;
}