简单dp
状态方程很好想，主要是初始化。。。。
代码：
1 #include<iostream> 2 #include<cstdlib> 3 #include<cstdio> 4 #include<cstring> 5 using namespace std; 6 #define MAX 1010 7 #define _INF -100000000 8 int n,m; 9 int f[MAX][MAX]; 10 int dp[MAX][MAX]; 11 int main() 12 { 13 int t; 14 scanf("%d",&t); 15 16 while(t--) 17 { 18 memset(f,0,sizeof(f)); 19 for(int i=0;i<MAX;i++) 20 for(int j=0;j<MAX;j++) 21 dp[i][j]=_INF; 22 scanf("%d%d",&n,&m); 23 for(int i=1;i<=n;i++) 24 for(int j=1;j<=m;j++) 25 scanf("%d",&f[i][j]); 26 dp[0][1]=0; 27 for(int i=1;i<=n;i++) 28 for(int j=1;j<=m;j++) 29 { 30 dp[i][j]=max(dp[i-1][j],dp[i][j-1]); 31 for(int k=1;k<j-1;k++) 32 if(j%k==0) dp[i][j]=max(dp[i][j],dp[i][k]); 33 dp[i][j]+=f[i][j]; 34 35 } 36 cout<<dp[n][m]<<endl; 37 } 38 return 0; 39 }