学步园

简单的动态规划 

#include<iostream>
#include<cstdio>
using namespace std;
int Max(int a,int b)
{
	if(a>b)
		return a;
	return b;
}
int main()
{
	int t,n,m,k,i,j,map[23][1003],dp[23][1003];
	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+1;i++)
			dp[i][0]=-9999;
		for(j=0;j<=m+1;j++)
			dp[0][j]=-9999;
		dp[1][1]=map[1][1];
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++)
			{
				if(i!=1||j!=1)
				{
					dp[i][j]=(dp[i-1][j]+map[i][j])>(dp[i][j-1]+map[i][j])?(dp[i-1][j]+map[i][j]):(dp[i][j-1]+map[i][j]);
					for(k=1;k<=j/2;k++)
						if(j%k==0)
							dp[i][j]=Max(dp[i][j],(dp[i][k]+map[i][j]));
				}
			}
		printf("%d\n",dp[n][m]);

	}
	return 0;
}