程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> hdu 4381 背包

hdu 4381 背包

編輯:關於C++

 

 

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 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.

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 si(1<=si<=2) , ai and xi (0 <= xi <= N,1<=ai<=N), si indicating the type of this operation, ai and xiindicating that the interval is [1,ai] or [ai,n](depending on si), and you can choose xi 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;
}


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved