[HDU] 2571命运 最基本的入门dp

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

方法：建立状态转移方程，设F(x,y)为当前走到获得的最大幸运值，current(x,y)为当前位置本来就具有的幸运值，则方程为：

　　　　{

　　　　　　0,　　x<1 or y<1;

F(x,y) = 　Max(  {F(x-1,y)+current(x,y)} U { F(x,yi)+current(x,y) | (yi%y==0 and yi!=y) or yi+1==y }  );　　

　　　　　　current(1,1),  x==1 and y==1;

　　　　}

在自底向上的时候，需要考虑一个位子列数c的小于c的真因子，注意找因子的方法是首先对c开根号，然后在从开根后的结果一个一个向1枚举，找到一个能整出c的数a后就自然找到另外一个能整除c的数c/a. 1作为c的平凡因子，这里只考虑1这个平凡因子的位子，不考虑c/1=c这个平凡因子的位子。

感谢：基本dp，入门练习专用。

代码：

#include<iostream>
#include<math.h>
using namespace std;
int const MAX =0x3f3f3f3f;
 
int matrix[21][1001];
int dp[21][1001];
int n,m;
int main()
{
    int tc=0,t;
    scanf("%d",&t);
    while(tc<t)
    {
        memset(matrix,0,sizeof(matrix));
        memset(dp,-MAX,sizeof(dp));
        scanf("%d %d",&n,&m);
        for(int i =1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                scanf("%d",&matrix[i][j]);
            }
        dp[1][1] = matrix[1][1];
        for(int i=2;i<=n;i++)
            dp[i][1] = dp[i-1][1]+matrix[i][1]; 
        for(int x= 1; x<=n;x++)
        {
            for(int i =2;i<=m;i++)
            {
                 if(matrix[x][i]+dp[x][i-1]>dp[x][i])
                    dp[x][i] = matrix[x][i]+dp[x][i-1];
                  if(matrix[x][i]+dp[x][1]>dp[x][i])
                    dp[x][i] = matrix[x][i]+dp[x][1];
                  int boundary =(int)sqrt(i+0.0); 
                  for(int k = 2; k<=boundary;k++)
                  {
                      if(i%k==0)
                      {
                         if(matrix[x][i]+dp[x][k]>dp[x][i])
                            dp[x][i] = matrix[x][i]+dp[x][k];
                         if(matrix[x][i]+dp[x][i/k]>dp[x][i])
                            dp[x][i] = matrix[x][i]+dp[x][i/k];
                      }
                  }

                  if(x>1)
                  {
                      if(matrix[x][i]+dp[x-1][i]>dp[x][i])
                        dp[x][i] = matrix[x][i]+dp[x-1][i];
                  }
            }
        }
        cout<<dp[n][m]<<endl;
        tc++;
    }
 
    return 0;
}