杭电2571-命运

  
1
3 8
9 10 10 10 10 -10 10 10
10 -11 -1 0 2 11 10 -20
-11 -11 10 11 2 10 -10 -10
这道题其实是一道DP（动态规划）题目，这题刚开始一看一位又是一道搜索题，但是题目的条件限制是单向不可以回头而且还可以是跳跃前进，所以用动态规划来解决，其动态转移方程：DP[i][j](表示是从起点到（i,j）点的最大值)，map[i][j]表示（i,j）该点的数值    方程为：DP[i][j]=Max(DP[i-1][j],DP[i][j-1])+map[i][j]；和DP[i][j]=Max(DP[i][j],DP[i][j/k]+map[i][j])（这个方程下面代码上注有解释
AC代码+解释：
#include<iostream>//DP
#include<cstring>
#include<cstdio>
#include<string>
#include<algorithm>
const int MAX=1001;
const int maxn=-999999;
int map[21][MAX];
int DP[21][MAX];//DP[i][j]表示从起点按规则走到（i,j）点的最大总值
int n,m;
using namespace std;
int Max(int x,int y)
{return x>y?x:y;
}
int main()
{int t,i,j;cin>>t;while(t--){cin>>n>>m;for(i=1;i<=n;i++){for(j=1;j<=m;j++){cin>>map[i][j];}}for(i=0;i<=n;i++)DP[i][0]=maxn;//边缘初始化for(i=0;i<=m;i++)DP[0][i]=maxn;//边缘初始化DP[0][1]=0;//注意初始化，始终保持DP[1][1]起点是map[1][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])+map[i][j];//开始走int k=2;while(j/k>0)//这里是表示可以从哪个点跳跃到该点{if(j%k==0)//如果可以跳跃DP[i][j]=Max(DP[i][j],DP[i][j/k]+map[i][j]);//比较是跳跃到该点总值大还是一步一步走过来的总值大k+=1;}}}cout<<DP[n][m]<<endl;//走到最后就求到了命运大迷宫中得到最大的幸运值}return 0;
}