首页 > ACM题库 > HDU-杭电 > hdu 3725 Farm待解决[解题报告]C++
2015
02-21

hdu 3725 Farm待解决[解题报告]C++

Farm

问题描述 :

Do you know the "Happy Farm"? It is a very popular webpage game. The player plays the role of the farmer, who can plant vegetables or grow kinds of flowers at his farm. When vegetables or flowers become ripe, the player can get in them in order to make some money. However, the greatest part of the game is to steal other farmers’ vegetables and flowers. The owner of the farm can keep a dog to help him guard against theft. Now, Farmer John intends to steal something when his neighbor David isn’t online.
Unfortunately, David keeps a dog. Can you work out a best plan for John?

Let’s suppose that David has planted n vegetables. The i-th vegetable’s value is vi. Meanwhile, stealing the i-th vegetable increases ai anger value of the dog. Due to the Internet and computer conditions, stealing the i-th vegetable will lead to an initial time delay of di. On the condition that we do not refresh the webpage, if you choose to steal the i-th vegetable in j-th turn, the actual time delay is j * di. Now, John wants to steal all of the vegetables. He can turn the dog’s anger value into zero and restart to count the number of delays by refreshing the webpage. Please pay attention that the value of the vegetable you are stealing now must be less than the value of any other vegetable that you have stolen before. It takes r units of time to refresh the webpage and the game allows you to refresh the webpage for m times at most.

During the whole theft, John wants to keep the maximum anger value of the dog at the lowest level. Meanwhile, the total time it takes cannot be longer than t units. Can you work out a plan?

输入:

The first line of input contain an integer T (T <= 10), indicating the number of test cases.

Each of the test cases must be organized in the following form. The first line of each case contain four integers n, m, r, t, (1 <= n <= 30000, 1 <= m <= 10, 1 <= r <= 100, 1 <= t <=260), with n representing the number of vegetables, m representing the maximum number for you to refresh the page, r representing the time it takes to refresh the page, and t representing the total time for John to commit his crime.

There must be three integers vi, ai, di, in each of the following n lines.The vi represents the value of each vegetable (just as there are no two same leaves in the world, so are the value of two vegetables).The ai represents the anger value of the dog. And the di represents the initial delay. 0 < vi <= 5*106, 0 < ai <= 100, n * ∑di can’t be larger than 262.

输出:

The first line of input contain an integer T (T <= 10), indicating the number of test cases.

Each of the test cases must be organized in the following form. The first line of each case contain four integers n, m, r, t, (1 <= n <= 30000, 1 <= m <= 10, 1 <= r <= 100, 1 <= t <=260), with n representing the number of vegetables, m representing the maximum number for you to refresh the page, r representing the time it takes to refresh the page, and t representing the total time for John to commit his crime.

There must be three integers vi, ai, di, in each of the following n lines.The vi represents the value of each vegetable (just as there are no two same leaves in the world, so are the value of two vegetables).The ai represents the anger value of the dog. And the di represents the initial delay. 0 < vi <= 5*106, 0 < ai <= 100, n * ∑di can’t be larger than 262.

样例输入:

3
4 1 1 10
4 2 1
3 2 3
1 2 1
2 2 1
4 0 1 13
4 2 1
3 2 3
1 2 1
2 2 1
4 0 1 14
4 2 1
3 2 3
1 2 1
2 2 1

样例输出:

6
I have no idea
8

Hint
For the first sample, John steals the first vegetable at the first time and the anger value increases to 2, costing time of 1*1. Then he refresh the webpage, and steals the 2nd ,4th and 3rd vegetable at the second time and the anger value increases to 6, costing time of 1*3+2*1+3*1 and the time of refreshing of 1,which adds to 10 of the total time. Considering that the anger value of the 2nd time comes to the largest, the answer is 6.For the second sample, John cannot refresh the page at all. He must steal the 1st, 2nd, 4th, 3rd in order, and the costing time is 1*1+2*3+3*1+4*1 = 14. Because the total allowed time is 13, so it isimpossible to steal all the vegetables.


  1. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }