免费馅饼(hdu1176)--一道典型的“数塔问题”。

Hdu1176免费馅饼,是一道典型的“数塔问题”。

（一）问题要求：

（1）从位置5开始走。

 （2）第0和第10个位置只有两个方向可以走，除此之外，第x个位置每次只有三个方向可以走。

   (3) 问题要找到一条路径使得馅饼总数目最大。

（二）问题描述：

根据（一）（2）中的描述，可以联系“数塔问题”的求解方法。“从底到上”求出所有子问题的解，并改变原来数组。

数据类型的选择：f[t][x]--表示第t(0秒在第x(0<=x<=10)个位置 掉下的馅饼数目。//f[0][x]=0,(0<=x<=10);

此题目可以描述为：求从f[0][5]到f[T][]的一条路径，使得总和最大。

（三）主要思路：

首先解决输入难的问题，根据（二）的描述，借鉴hdu论坛的方法，选择（二）中的数据类型 。

然后即为求解过程，此题与数塔求解有点不同。数塔从底到上比较时，每个元素的改变只与其左右下一个元素有关，而这个题目根据题意（人站在原点也可以接到馅饼）每个元素的改变与下面三个元素有关，当然第1个、第10个位置的改变与两个元素有关。

其他的就差不离了。

（四）程序代码：

//免费馅饼,数塔问题。

#include

 

//关键是数据类型的选择：f[t][x]--表示第t(0秒在第x(0<=x<=10)个位置 掉下的馅饼数目。

//f[0][x]=0,(0<=x<=10);

//问题描述为：求从f[0][5]到f[T][]的一条路径，使得总和最大。

 

int f[100001][11];

 

inline int max(int a,int b)

{return a>b?a:b;

}

inline int max2(int a,int b,int c)

{return max(max(a,b),max(b,c));

}

 

int main()

{

 int n,x,t,i,j,maxt;

 while(scanf("%d",&n)!=EOF&&n)

 {

       for(t=0;t<=100001;t++)

          for(x=0;x<=10;x++) f[t][x]=0;

 maxt=0;

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

       {scanf("%d%d",&x,&t);

        f[t][x]++;//

          maxt=max(maxt,t);

       }//输入完毕

    //maxt：时间的最大值

 

       for(i=maxt;i>=1;i--)//n---1--0

         for(j=0;j<=10;j++)//0,1-9,10

         {

              if(j==0) //0

              {

               f[i-1][j]+=max(f[i][j],f[i][j+1]);

              }

        else if(j==10) //10

              {

               f[i-1][j]+=max(f[i][j],f[i][j-1]);

              }

              else//1---9

              {f[i-1][j]+=max2(f[i][j-1],f[i][j],f[i][j+1]);//三个数的最值

              }

         }//for j

 

       printf("%d\n",f[0][5]);

 }

 

       return 1;

}