命运

T T 过了测试数据和自己造的数据后始终WA。。和人家的动归数组完全一样。。不知道哪里没有想到。。mark一下，过两天再看下。。

自己的WA =。 =

#include <iostream>
#include <cstring>
#define N 22
#define M 1005
using namespace std;

int factor[M][M];

void fac()
{
    int ret[M] = {0};
    for(int j=1; j<M; j++)
    {
        int index = 0 ;
        for(int i=1; i<j/2+1; i++)
        {
            if(j%i==0) 
            {
                ret[index] = i;
                index++;
            }
        }
        for(int i=0; i<M; i++)
            factor[j][i] = ret[i];
        memset(ret, 0, sizeof(ret));
    }
}

int main()
{
    int c, n, m, ans, k, t;
    int num[N][M];
    int dp[N][M];
    fac();
    factor[1][1] = 1;
//    for(int i=0; i<55; i++)
//    {
//        cout << i << ": ";
//        for(int j=0; j<25; j++)
//            cout << factor[i][j] << " " ;
//        cout << endl;
//    }
    cin >> c;
    while(c--)
    {
        cin >> n >> m;
        memset(num, 0, sizeof(num));
        memset(dp, 0, sizeof(dp));
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
                cin >> num[i][j];
        dp[1][1] = num[1][1];
        
        //i=1
        for(int j=2; j<=m; j++)
        {
            t = dp[1][j-1];
            for(int k=1; factor[j][k]; k++)
            {
                t = max(t, dp[1][factor[j][k]]);
            }
            //dp[1][j] = max(dp[1][j-1], dp[1][j de yinzi]) + num[1][j];
            dp[1][j] = t + num[1][j];
        }

        for(int i=2; i<=n; i++)
        {
            dp[i][1] = dp[i-1][1] + num[i][1];
            for(int j=2; j<=m; j++)
            {
                t = max(dp[i-1][j], dp[i][j-1]);
                for(int k=1; factor[j][k]; k++)
                {
                    t = max(t,dp[i][factor[j][k]]);
                }
                dp[i][j] = t + num[i][j];
            }
        }
//        cout << endl;
//        for(int i=0; i<=n; i++)
//        {
//            for(int j=0; j<=m; j++)
//            {
//                cout << dp[i][j] << " " ;
//            }
//            cout << endl;
//        }
        cout << dp[n][m] << endl;
    }
    return 0;
}

人家的AC

/*
  此题状态转移方程很容易想，定义dp[i][j]为到达第i行第j列时的幸运值
  那么dp[i][j]=max(dp[i-1][j]+ary[i][j],dp[i][j-1]+ary[i][j],dp[i][j/k]+ary[i][j])（j%k==0&&k>1)
  然而一开始对初始化没处理好，而且没考虑到从左上角到右下角，至少有n+1个格子是必走的（包括左上角和右下角）,贡献若干WA
  解决方法是，对i,j进行特判，如果j==1，那么他只能从它的正上方走下来一格，i==1则只能从左边走来。
  
  62MS    392K
  */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int ary[25][1005];
int dp[25][1005];
int n,m;

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                scanf("%d",&ary[i][j]);
                dp[i][j] = ary[i][j];
            }
        }
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                if(j == 1 && i == 1)
                    continue;
                if(j == 1)
                {
                    dp[i][j] = dp[i-1][j]+ary[i][j];
                    continue;
                }
                int temp = 0;
                if(i != 1)
                    temp = max(dp[i-1][j]+ary[i][j],dp[i][j-1]+ary[i][j]);
                else
                    temp = dp[i][j-1]+ary[i][j];
                int k = 2;
                while(j/k)
                {
                    if(j%k == 0)
                        temp = max(temp,dp[i][j/k]+ary[i][j]);
                    k ++;
                }
                dp[i][j] = temp;
            }
        }
        printf("%d\n",dp[n][m]);
    }
    return 0;
}