HDU1078
HDU1078
这个题我们可以看出每个点不管之前怎么走，之后能走的最大路径都是固定的，因为之前不管怎么走，只要走到了这个点，就说明没有走过比当前点权值大的点，所以我们可以记忆化搜索一下，就可以了。
HDU1078代码
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 105;
int dp[maxn][maxn];
int v[maxn][maxn];
int dis[4][2]={
1,0,-1,0,0,1,0,-1};
int n,k;
int dfs(int x,int y)
{if(dp[x][y]!=-1) return dp[x][y];dp[x][y]=v[x][y];for(int i=1;i<=k;i++){for(int j=0;j<4;j++){int tx=x+dis[j][0]*i;int ty=y+dis[j][1]*i;if(tx<1||tx>n||ty<1||ty>n) continue;if(v[tx][ty]<=v[x][y]) continue;dp[x][y]=max(dp[x][y],v[x][y]+dfs(tx,ty));}}return dp[x][y];
}
int main()
{while(scanf("%d%d",&n,&k)!=EOF){if(n==-1&&k==-1) break;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){scanf("%d",&v[i][j]);dp[i][j]=-1;}}printf("%d\n",dfs(1,1));}return 0;
}