学步园

题意：中文题，略

按题意模拟转移方程就可以了

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <queue>
#include <vector>
#define inf 1000000000
#define N 100010
#define ll int
using namespace std;
inline ll Max(ll a,ll b){return a>b?a:b;}

int n,m,map[30][1005];
int dp[30][1005];
int main(){
    int T,i,j;scanf("%d",&T);
    while(T--){
        scanf("%d %d",&n,&m);
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
                scanf("%d",&map[i][j]);

        dp[1][1]=0;
        for(i=1;i<=m;i++)dp[1][i]=dp[1][1]+map[1][i];
        for(i=2;i<=n;i++)
            for(j=1;j<=m;j++)
                dp[i][j]=dp[i-1][j]+map[i][j];
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                if(i>1)
                    dp[i][j]=Max(dp[i][j],dp[i-1][j]+map[i][j]);
                dp[i][j+1]=Max(dp[i][j+1],dp[i][j]+map[i][j+1]);
                for(int k=2;j*k<=m;k++)
                    dp[i][j*k]=Max(dp[i][j*k],dp[i][j]+map[i][j*k]);
            }
            printf("%d\n",dp[n][m]);            
    }
    return 0;
}