hdu 2571 命运 （递推）

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

思路：

    

dp[i+1][j]=max(dp[i+1][j],dp[i][j]+mat[i+1][j]);
                dp[i][j+1]=max(dp[i][j+1],dp[i][j]+mat[i][j+1]);
                k=2;
                while(k*j<=m)
                {
                    dp[i][k*j]=max(dp[i][k*j],dp[i][j]+mat[i][k*j]);
                    k++;
                }

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
#define INF 1000000000
int mat[30][2000];
int dp[30][2000];
int main()
{
    int t,n,m;
    int i,j,k;
    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]=-INF;
                scanf("%d",&mat[i][j]);
            }
        }
        dp[1][1]=mat[1][1];
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                dp[i+1][j]=max(dp[i+1][j],dp[i][j]+mat[i+1][j]);
                dp[i][j+1]=max(dp[i][j+1],dp[i][j]+mat[i][j+1]);
                k=2;
                while(k*j<=m)
                {
                    dp[i][k*j]=max(dp[i][k*j],dp[i][j]+mat[i][k*j]);
                    k++;
                }
            }
        }
        /*for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                printf("%d ",dp[i][j]);
            }
            cout<<endl;
        }*/
        printf("%d
",dp[n][m]);
    }
    return 0;
}