运用二维数组的一个道简单dp的题目。
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<stdlib.h>
#define INF_MAX 0x7fffffff
#define INF 999999
#define max3(a,b,c) (max(a,b)>c?max(a,b):c)
#define min3(a,b,c) (min(a,b)<c?min(a,b):c)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
struct node
{int u;int v;int w;bool friend operator < (node a, node b){return a.w < b.w;}
}edge[1001];
int gcd(int n,int m){if(n<m) swap(n,m);return n%m==0?m:gcd(m,n%m);}
int lcm(int n,int m){if(n<m) swap(n,m);return n/gcd(n,m)*m;}
int main()
{int T,i,m,n;int j,k;int map[21][1001];int dp[21][1001];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]);}}for(i=1;i<=n;i++){for(j=1;j<=m;j++)dp[i][j]=-INF_MAX;}for(i=0;i<=m;i++)dp[0][j]=0;dp[1][1]=map[1][1];for(i=1;i<=n;i++){for(j=1;j<=m;j++){if(i+1<=n)dp[i+1][j]=max(dp[i+1][j],dp[i][j]+map[i+1][j]);if(j+1<=m)dp[i][j+1]=max(dp[i][j+1],dp[i][j]+map[i][j+1]);for(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;
}