[HDU]2571命运

http://acm.hdu.edu.cn/showproblem.php?pid=2571

这又是一题升级版的数塔.

如果当前格子是（x,y），下一步可以是（x+1,y），(x,y+1)或者(x,y*k) 其中k>1,这句话是什么意思呢?

举个例子从(1,1)到(1,4)可以按最规范的走法(1,1)(1,2)(1,3)(1,4);也可以(1,1)(1,2)(1,4);还可以(1,1)(1,4)

这样的话,计算每个位置的最大值时,还要依次与该行步数y的分子比较;

还有一个问题就是边界问题,(1,1)是很明显的边界,所以我避开了它.

把这个二维方格矩阵分成了3部分,1是第一行,2是第一列,3是其余的各个部分

#include"stdio.h"
#include"stdlib.h"
int dp[25][1010];                                       //保存每个位置的最大值 
int maxabc(int a,int b)
{
    int max;
    max=a>b?a:b;
    return max;
}
int main()
{
      int t,n,m,i,j,k,max,temp1,temp2,temp3;
      scanf("%d",&t);
      while(t--)
      {
             scanf("%d%d",&n,&m); 
             for(i=1;i<=n;i++)                              //初始化,不过应该不用初始也没关系,因为接下来已经全部赋值            
              for(j=1;j<=m;j++)
              dp[i][j]=0;
             for(i=1;i<=n;i++)
              for(j=1;j<=m;j++)
               scanf("%d",&dp[i][j]);
             for(j=2;j<=m;j++)                              //第一行的处理(不包括第一行第一个) 
             {
                     max=dp[1][j-1];
                     for(k=1;k<j;k++)                          
                     {
                          if(j%k==0)
                          {
                             temp1=dp[1][k];                    //友情提示:1不要打成i,要不找半天都找不出哪错了,,,, 
                             max=maxabc(max,temp1);
                          }
                     }                    
                     dp[1][j]+=max;
             } 
             for(i=2;i<=n;i++)                             //第一列的处理(不包括第一行第一个) 
             dp[i][1]+=dp[i-1][1];
             for(i=2;i<=n;i++)
              for(j=2;j<=m;j++)                            //剩余情况的处理 
             {
                   temp1=dp[i][j-1];
                   temp2=dp[i-1][j];
                   max=maxabc(temp1,temp2);
                   for(k=1;k<j;k++)
                   {
                       if(j%k==0)
                       {
                          temp3=dp[i][k];
                          max=maxabc(max,temp3);
                       }
                   }
                   dp[i][j]+=max;
             }
             printf("%d
",dp[n][m]);
      }
     // system("pause");
}