hdu1176 参考答案

   1 /*
   2 hdu1176 DP：免费馅饼
   3 ymc 2008/09/22
   4 题目大意：
   5 人在一个[0,10]的小径上,天上会掉馅饼。
   6 总共有n个馅饼，每个馅饼在t时刻掉到x位置。
   7 初始位置人在x=5位置,人一秒中最多左右移动1的距离。
   8 求最多能接住多少个馅饼。
   9 分析与解题思路
  10 用map[t][x]记录在t时刻掉在x位置的馅饼个数。
  11 用ans[t][x]记录在t时刻人在x位置的时候最多能接住多少
  12 个馅饼。
  13 则在|x-5|<=t时
  14 ans[t][x]=Max{ans[t-1][x-1],ans[t-1][x],ans[t-1][x+1]}+map[t][x];
  15 注意：N＝100000时会WA，晕死。
  16 */
  17 #include <iostream>
  18 #include <cmath>
  19 using namespace std;
  20 const int N=100005;
  21 const int M=11;
  22 int map[N][M];
  23 int n;
  24 int ans[N][M];
  25 int step[2]={1,-1};
  26 int mt;
  27 void DP()
  28 {
  29     int Max;
  30     int x1;
  31     int MaxOut=0;
  32     memset(ans,0,sizeof(ans));
  33 //    ans[0][5]=map[0][5];
  34     for(int t=1;t<=mt;t++)
  35     {
  36         for(int x=0;x<=10;x++)
  37         {
  38             if(abs(x-5)>t)
  39                 continue;
  40             Max=ans[t-1][x];
  41             for(int k=0;k<2;k++)
  42             {
  43                 x1=x+step[k];
  44                 if(x1<0||x1>10)
  45                     continue;
  46                 if(Max<ans[t-1][x1])
  47                     Max=ans[t-1][x1];
  48             }
  49             ans[t][x]=Max+map[t][x];
  50             if(ans[t][x]>MaxOut)
  51                 MaxOut=ans[t][x];
  52         }
  53     }
  54 
  55     printf("%d\n",MaxOut);
  56 }
  57 int main()
  58 {
  59     int x,t;
  60     while(scanf("%d",&n),n)
  61     {
  62         memset(map,0,sizeof(map));
  63         mt=0;
  64         for(int i=0;i<n;i++)
  65         {
  66             scanf("%d %d",&x,&t);
  67             map[t][x]++;
  68             if(t>mt)
  69                 mt=t;
  70         }
  71         DP();
  72     }
  73 }