dp or 貪心 --- hdu : Road Trip

Road Trip

Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:65536KB

Total submit users: 29, Accepted users: 29

Problem 12882 : No special judgement

Problem description

You are planning a road trip to visit your friends, each of whom live in different towns. Of course, you don't want to pay any more for fuel on the trip than you need to. However, the price of fuel in each of the towns is different, so you will need to carefully plan the trip to minimise the cost. For example, it might make sense to take on extra fuel at a town where the price is low so that you don't need to buy so much at a town where it is more expensive. Indeed, it may even make sense to sell excess fuel at some towns to recoup some of the costs. Of course, your car can only hold a certain amount of fuel, and you have to make sure you take on enough fuel at each town to reach the next (assume that it's OK to arrive with an empty tank).

Your task is to write a program to

help you plan your trip.

Input

Input will consist of specifications for a series of journeys. Information

for each journey will begin with a line containing an integer 0 < c < 100

that specifies the capacity of the car's fuel tank in litres and an integer 0

< t < 20 that specifies the number of towns to visit for that journey. A

line containing two zeros indicates the end of input.

The following t lines

contain information about successive stages on the journey: the price (in fixed

point dollars-and-cents format, 0.01 <= p < 9.99) of one litre of fuel

(either to buy or to sell) in the town at the beginning of the stage, and the

number of litres of fuel (an integer, 1 <= n < 100) needed to reach the

next town.

Output

Output should consist of one line for each journey comprising the journey

number (formatted as shown) followed by a single space and the minimum cost of

completing that journey, formatted as a fixed-point number with 2 decimal

places.

Sample Input

Sample Output

Problem Source

HNU Contest 

Mean:

你要開車去n個小鎮拜訪你的老朋友，但是你不是高富帥，隻得将油錢盡量的省，現在給你油箱的容量、小鎮數量、每個小鎮的油價、到達下一個小鎮需要的油，你可以買油也可賣油，問你最少的油錢是多少。

analyse:

這題就是一個貪心的思想，如果下一站的油價比這站高，那麼别想了，将油箱裝滿，到下一站就可以賺錢；反之就隻需買夠路上用的就可。

當然有人說這題是dp，這也沒錯，看個人怎麼了解，其實這題就兩個狀态之間轉移，dp已經退化為貪心。

Time complexity：O(n)

Source code：

//Memory   Time

// 1254K    0MS

// by : Snarl_jsb

#include<algorithm>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<vector>

#include<queue>

#include<stack>

#include<iomanip>

#include<string>

#include<climits>

#include<cmath>

#define MAX 110

#define LL long long

using namespace std;

struct Node

{

   double p;

   int next;

};

Node node[MAX];

int v,n;

int main()

   int kase=1;

   while(scanf("%d %d",&v,&n),v+n)

   {

       double cost=0.0;

       printf("Journey %d: ",kase++);

       bool flag=0;

       for(int i=1;i<=n;i++)

       {

           scanf("%lf %d",&node[i].p,&node[i].next);

           if(node[i].next>v)

           {

               flag=1;

               break;

           }

       }

       if(flag==1)

           puts("0.00");

           continue;

       int now=0;

       for(int i=1;i<n;i++)   //zui hou mei pan

            if(i>1) // begin to No.2

               if(node[i].p>node[i-1].p&&now>node[i].next)   //sell

               {

                   int tmp=now-node[i].next;

                   cost-=node[i].p*tmp;

                   now-=tmp;

               }

           if(node[i].p<node[i+1].p)   //  earn money

               int tmp=v-now;

               cost+=node[i].p*tmp;

               now=v-node[i].next;

           else    // bu ke zhuan qian

               int tmp;

               if(node[i].next>now)

                   tmp=node[i].next-now;

                   now=0;

               else

                   tmp=0;

                   now-=node[i].next;

       // final

       if(now>node[n].next)

           int tmp=now-node[n].next;

           cost-=tmp*node[n].p;

           now=0;

       else

           int tmp=node[n].next-now;

           cost+=tmp*node[n].p;

       printf("%.2lf\n",cost);

   }

   return 0;

}