首页 > 代码库 > HDU 2571 命运 简单的DP

HDU 2571 命运 简单的DP

题目链接  ~~   http://acm.hdu.edu.cn/showproblem.php?pid=2571

题意很简单,就是求左上角到右下角的最大值。

刚开始忘了初始化。。WA好几回。。

代码::

 1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4 #define  max(a,b) (a>b?a:b) 5 int main() 6 { 7     int map[25][1005]; 8     int dp[25][1005]; 9     int t,n,m,i,j,k;10     scanf("%d",&t);11     while(t--)12     {13          scanf("%d%d",&n,&m);14          for(i=1;i<=n;i++)15             for(j=1;j<=m;j++)16             {17                 scanf("%d",&map[i][j]);18                 dp[i][j]=-999;19             }20          dp[1][1]=map[1][1];21          for(i=1;i<=n;i++)22             for(j=1;j<=m;j++)23             {24                /*if(i==1&&j==1)25                {26                    dp[i][j]=map[i][j];27                    continue;28                }*/29                if(i>1)30                  dp[i][j]=max(dp[i][j],dp[i-1][j]+map[i][j]);31                if(j>1)32                  dp[i][j]=max(dp[i][j],dp[i][j-1]+map[i][j]);33                for(k=1;k<j;k++)34                  if(j%k==0)35                     dp[i][j]=max(dp[i][j],dp[i][k]+map[i][j]);36             }37          printf("%d\n",dp[n][m]);38     }39 40   return 0;41 }

 

HDU 2571 命运 简单的DP