Chinaunix首页 | 论坛 | 博客
  • 博客访问: 104299
  • 博文数量: 27
  • 博客积分: 1400
  • 博客等级: 上尉
  • 技术积分: 290
  • 用 户 组: 普通用户
  • 注册时间: 2009-10-26 15:43
文章分类

全部博文(27)

文章存档

2011年(1)

2010年(8)

2009年(18)

我的朋友

分类: C/C++

2009-11-05 16:52:10

题目:
Candy的魔法
Submit: 646   Accepted:113
Time Limit: 1000MS  Memory Limit: 65536K
Description
小蚂蚁的家在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;
}


阅读(1482) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~