HDU 2571 命运 （DP）

#include<stdio.h>
int T,n,m,a[50][1005],dp[50][1005];
int Max(int a,int b)
{
    return a>b?a:b;
}
void In()   //各种初始化
{
    scanf("%d%d",&n,&m);
    int i,j;
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            scanf("%d",&a[i][j]);
    dp[1][1]=a[1][1];
    for(i=2; i<=m; i++)    //计算上边界
    {
        dp[1][i]=dp[1][i-1]+a[1][i];
        for(j=1; j<i; j++)
            if(i%j==0 && dp[1][j]+a[1][i]>dp[1][i])
                dp[1][i]=dp[1][j]+a[1][i];
    }
    for(i=2; i<=n; i++)   //计算左边界
        dp[i][1]=dp[i-1][1]+a[i][1];
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        In();
        int i,j;
        for(i=2; i<=n; i++)   //DP
            for(j=2; j<=m; j++)
            {
                dp[i][j]=Max(dp[i-1][j],dp[i][j-1])+a[i][j];
                for(int k=1; k<j; k++)
                    if(j%k==0 && dp[i][k]+a[i][j]>dp[i][j])
                        dp[i][j]=dp[i][k]+a[i][j];
            }
        printf("%d\n",dp[n][m]);
    }
    return 0;
}