首页 > ACM题库 > HDU-杭电 > HDU 1692 Destroy the Well of Life-枚举-[解题报告] C++
2013
12-21

HDU 1692 Destroy the Well of Life-枚举-[解题报告] C++

Destroy the Well of Life

问题描述 :

In the game of DotA (Defense of the Ancient), there are two opposite legions called The Sentinel and The Scourage.
Now The Scourage has made a big success and The Sentinel is at stake!
So The Sentinel must destroy the Well of Life of The Scourage.
The chief of The Sentinel, Prophet, asks EarthShaker to do this arduous task.There are N Wells of Life of The Scourage (The Wells of Life are numbered from 1 to N), and EarthShaker’s task is to destroy the Nth Well of Life.
The following information is known about each Well of Life:
Wi � the weight of water on i-th Well of Life before it is destroyed.
Li � if the weight of water on i-th Well of Life is more than Li, the i-th Well of Life will be destroyed and the water of it will pours to the (i + 1)-th Well of Life.
Pi � EarthShaker has a skill called Echo-Slam, the i-th Well of Life will be immediately destroyed when he uses Echo-Slam to it and the water of it will pours to the (i + 1)-th Well of Life. For the i-th Well of Life, the energy that EarthShaker need to use Echo-Slam to destroy it is Pi.

Can you tell EarthShaker the minimum amount of energy needed to destroy the Nth Well of Life?

输入:

The input consists of several test cases. There is a single number on the first line, the number of cases. There are no more than 10 cases.
Each case contains a natural number N on the first line, 1<=N<=100,000.
Following N lines contains three numbers Wi, Li, Pi (Wi<=Li, 0<=Wi, Li, Pi <=20,000), representing the information of the i-th Well of Life.

输出:

For each case, print a number in a line representing the least amount of energy EarthShaker needed to use, so as to destroy the Nth Well of Life. Use the format in the sample.

样例输入:

1
3
1000 1000 1 
0 1000 2 
2 10 100

样例输出:

Case 1: Need to use 3 mana points.

题目分析:
重点:要摧毁第N个井,而不是n个井,在这我纠结了好长时间
思路:可以从1->n也可以N->1选出最小的就ok了
技巧:不能暴力求最小值,会超时;巧用break;
#include<stdio.h>
int l[100001];
int r[100001];
int sum[100001];
int main()
{
    //freopen("e:1.txt","r",stdin);
    int n,T,t=0;
    scanf("%d",&T);
    
    while(T--)
    {
        int i,max;
        scanf("%d",&n); 
        for(i = 0;i < n;i++)
            scanf("%d%d%d",&l[i],&r[i],&sum[i]);
        int min=sum[n-1],msum;
        for(i=0;i<n-1;i++)
        {
            max=0;
            msum=0;
            for(int j = i;j < n;j++)
            {
                max+=l[j];
                if(max <= r[j]) msum+=sum[j];
    
                if(msum>min) break;
            }
            if(msum < min) 
                min=msum;
        }
        printf("Case %d: Need to use %d mana points.\n",++t,min);
    }
    return 0;
} 

解题报告转自:http://www.cnblogs.com/skyming/archive/2011/08/15/2139715.html


  1. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)

  2. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。