题意：

中文题

要点：

期末考试考完了，继续刷题。这题就是个简单的DP，多决策分析，可以向右移一格，向下移一格，或是向右移动到当前列的倍数。状态转移方程很容易写出来是：

dp[i][j]=max(dp[i-1][j],dp[i][j-1],dp[i][j/k])，注意这题有负数，边界条件设为一个较小的负数。

17416416

2016-07-01 13:44:29

Accepted

327MS

1584K

G++

#include
    
     #include
     
      #include
      
       using namespace std;int main(){	int dp[25][1005],map[25][1005];	int t, n, m;	int i, j, k;	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 = 0; i <= n; i++)			dp[i][0] = -0xfffff;		for (i = 0; i <= m; i++)			dp[0][i] = -0xfffff;		dp[0][1] = dp[1][0] = 0;		for(i=1;i<=n;i++)			for (j = 1; j <= m; j++)			{				dp[i][j] = max(dp[i - 1][j], dp[i][j-1]);				for (k = 2; k <= m; k++)					if (j / k == (double)j / k)//判断k是否为因数						dp[i][j] = max(dp[i][j], dp[i][j / k]);				dp[i][j] += map[i][j];			}		printf("%d\n", dp[n][m]);	}	return 0;}