hdu5188 加限制的01背包問題

hdu5188 加限制的01背包問題

 

 

Problem Description As one of the most powerful brushes in the world, zhx usually takes part in all kinds of contests.
One day, zhx takes part in an contest. He found the contest very easy for him.
There are n problems in the contest. He knows that he can solve the ith problem in ti units of time and he can get vi points.
As he is too powerful, the administrator is watching him. If he finishes the ith problem before time li, he will be considered to cheat.
zhx doesn't really want to solve all these boring problems. He only wants to get no less than w points. You are supposed to tell him the minimal time he needs to spend while not being considered to cheat, or he is not able to get enough points.
Note that zhx can solve only one problem at the same time. And if he starts, he would keep working on it until it is solved. And then he submits his code in no time.
Input Multiply test cases(less than 50). Seek EOF as the end of the file.
For each test, there are two integers n and w separated by a space. (1≤n≤30, 0≤w≤109)
Then come n lines which contain three integers ti,vi,li. (1≤ti,li≤105,1≤vi≤109)
Output For each test case, output a single line indicating the answer. If zhx is able to get enough points, output the minimal time it takes. Otherwise, output a single line saying zhx is naive! (Do not output quotation marks).
Sample Input

1 3
1 4 7
3 6
4 1 8
6 8 10
1 5 2
2 7
10 4 1
10 2 3

Sample Output

7
8
zhx is naive!

/**
hdu5188 有限制條件的01背包問題
題目大意：有n道題i題用時ti秒，得分vi，在li時間點之前不能做出來，而且一道題不能分開幾次做（一旦開始做，必須在ti時間內把它做完）
          問得到w分的最小用時是多少
解題思路：很像01背包的基本題，但是有一個li分鐘前不能AC的限制，因此第i道題必須在最早第（li-ti）時刻做，我們按照l-t遞增排序，然後按照經典解法來做
          就行了
*/
#include 
#include 
#include 
#include 
using namespace std;

struct note
{
    int t,v,l;
    bool operator <(const note &other)const
    {
        return l-tsum)
        {
            printf(zhx is naive!
);
            continue;
        }
        sort(node,node+n);
        up=max(up,ans);
        memset(dp,0,sizeof(dp));
        for(int i=0;i=node[i].l;j--)
            {
                if(j>=node[i].t)
                {
                    dp[j]=max(dp[j],dp[j-node[i].t]+node[i].v);
                }
            }
        }
        int flag=0;
        for(int i=0;i<=up;i++)
        {
            if(dp[i]>=m)
            {
                printf(%d
,i);
                flag=1;
                break;
            }
        }
        if(flag==0)
        {
            printf(zhx is naive!
);
        }
    }
    return 0;
}

 

Problem Description As one of the most powerful brushes in the world, zhx usually takes part in all kinds of contests.
One day, zhx takes part in an contest. He found the contest very easy for him.
There are n problems in the contest. He knows that he can solve the ith problem in ti units of time and he can get vi points.
As he is too powerful, the administrator is watching him. If he finishes the ith problem before time li, he will be considered to cheat.
zhx doesn't really want to solve all these boring problems. He only wants to get no less than w points. You are supposed to tell him the minimal time he needs to spend while not being considered to cheat, or he is not able to get enough points.
Note that zhx can solve only one problem at the same time. And if he starts, he would keep working on it until it is solved. And then he submits his code in no time.
Input Multiply test cases(less than 50). Seek EOF as the end of the file.
For each test, there are two integers n and w separated by a space. (1≤n≤30, 0≤w≤109)
Then come n lines which contain three integers ti,vi,li. (1≤ti,li≤105,1≤vi≤109)
Output For each test case, output a single line indicating the answer. If zhx is able to get enough points, output the minimal time it takes. Otherwise, output a single line saying zhx is naive! (Do not output quotation marks).
Sample Input

1 3
1 4 7
3 6
4 1 8
6 8 10
1 5 2
2 7
10 4 1
10 2 3

Sample Output

7
8
zhx is naive!