学步园

来源：点击打开链接

看上去像是搜索，但是还是用的dp。

建图，然后观察发现下一步的状态，取决于上一步的状态。其中dp[1][1]=原图的起点。然后for each i->m j->n 2<k,m/j)下一步有max(dp[i-1][j],dp[i][j-1] dp[i][j*k])+mat[i][j],三种状态都列举一遍，直接出数就可以了。

注意初始化为-inf，开始只从0->m，wa了一遍，应该是从0至少到m+1进行初始化。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;

int dp[25][1005];
int mat[25][1005];
const int NINF=-0x3f3f3f3f;

int main()
{
	int testcase;
	cin>>testcase;
	while(testcase--)
	{
		int res=0;
		int n,m;
		memset(mat,0,sizeof(mat));

		cin>>n>>m;
		for(int i=0;i<=n+2;i++)
			for(int j=0;j<=m+2;j++)
				dp[i][j]=NINF;   //多初始化两个。。 
				
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
				cin>>mat[i][j];
				
		dp[1][1]=mat[0][0];
		
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				dp[i+1][j]=max(dp[i+1][j],dp[i][j]+mat[i][j-1]);  //第一种 
				dp[i][j+1]=max(dp[i][j+1],dp[i][j]+mat[i-1][j]);  //第二种 
				for(int k=2;j*k<=m;k++)
				{
					dp[i][j*k]=max(dp[i][j*k],dp[i][j]+mat[i-1][(j*k)-1]);  //第三种 
				}
			}
		
		}
		cout<<dp[n][m]<<endl;
	
	}
	return 0;
}