bupt oj 1074 解题报告

题目：
Candy的魔法Submit: 646   Accepted:113Time Limit: 1000MS  Memory Limit: 65536KDescription
小蚂蚁的家在X轴的原点上，他的学校在X轴的N点上。
小蚂蚁从家里出发，沿X轴正方向前进（不能往回走），去学校里上课，他的本能速度是每两秒一个单位。由于小蚂蚁的速度之慢，老师担心他会迟到，就在途中的 某些点上放了具有魔法的糖果（每个位置要么没放，要么只放了一个），每个糖果有一定的魔法值b，他能使小蚂蚁将以每秒1个单位的速度移动b秒，在这个魔法 期间之内它只能向前移动，不能停下，也不能吃其他糖果。当然了，小蚂蚁可以自己选择是否要吃糖果，以及吃哪些位置上的糖果。他也只能朝向学校的方向走，而 不能掉头。
现在给出你学校的位置N，以及糖果的放置情况，请你计算小蚂蚁到达学校至少需要多久。


Input
多组数据测试。数据以两个0结束输入。
每组数据包括两部分：第一行两个整数N（1< N <= 1000000000），M(0 <= M <= 50)，N为学校的位置，M表示老师在途中放置的糖果的数目；
接下来的M行里，每行两个整数a（1<= a <= N），b（1<=b<=10000），a表示糖果位置，b表示对应糖果的魔法值。


Output
对每一组测试输出，输出小蚂蚁至少需要多少时间才能到达学校。每组数据的输出应该占一行。

Sample Input

7 2
2 2
3 4
5 3
3 1
1 2
4 2
0 0


Sample Output

10
7

思路：

   这个题属于动态规划问题。首先按从小到大的顺序排列有糖果的点。然后从后（结尾m）向前遍历每一个有糖果的点。用dp[i]存储第i个有糖果的点的所使用的最大魔法值。以为在每个有糖果得点有两种选择，即使用这个点的魔法或者不使用。然后比较使用这点魔法或者不适用后总的使用魔法量，选取较大值作为此点的dp[i]。
   假如使用i点的魔法 则总的魔法使用量变为 mag[i] + dp[j] ，j点为 pos[i]+mag[i]后免得的第一个有魔法值的点。如果不适用i点的魔法 则使用的魔法总量为dp[i+1] 。比较两个值，取较大的。这样一直循环到dp[0]就是使用魔法的最大量。
   此题是取i点使用魔法的总和作为动态规划的内容。

CODE：

#include<stdio.h>
#include<stdlib.h>
 
main()
{
      long n,pos[60],tmp,tem,max,dp[60];
      int m,i,j,mag[60],temp;
      scanf("%ld%d",&n,&m);
      while(n||m)
      {
           for(i=0;i<=m-1;i++)
               scanf("%ld%d",&pos[i],&mag[i]);
           for(i=0;i<=m-2;i++)
              for(j=i+1;j<=m-1;j++)
              {
                  if(pos[i]>pos[j])
                  {
                      tem=pos[i];
                      pos[i]=pos[j];
                      pos[j]=tem;
                      temp=mag[i];
                      mag[i]=mag[j];
                      mag[j]=temp;
                  }
              }
           
           pos[m]=n;
           dp[m]=0;
           dp[m+1]=0;
           for(i = m-1;i >= 0;i--){
                 if(pos[i] + mag[i] > pos[m]){
                     dp[i] = dp[i+1];
                 }
                 else if( pos[i] + mag[i] <= pos[i+1]){
                     dp[i] = mag[i] + dp[i + 1];
                 }
                 else{
                      
                      for(j = m; pos[j] >= pos[i] + mag[i]; j--);
                      tmp = mag[i] + dp[j+1 ];
                      if(tmp >= dp[i+1]) dp[i] = tmp;
                      else dp[i] = dp[i+1];
                 }
           }
           
           printf("%ld\n",dp[0]+2*(n-dp[0]));
           scanf("%ld%d",&n,&m);
      }
      
      //system("pause");

      return 0;
}