西安网站建设维护,网站建设公司哪里好,iis wordpress 403,常州网站推广软件信息FatMouse and Cheese HDU - 1078 这道题需要说一说#xff0c;定义dp[x][y]表示从点(x,y)出发#xff0c;每次走不超过k步#xff0c;所能吃到的最大量。 
有点难搞的是#xff0c;这里递归的顺序不好确定#xff0c;所以采用自顶向下的记忆化搜索的方式#xff08;不用担… FatMouse and Cheese HDU - 1078 这道题需要说一说定义dp[x][y]表示从点(x,y)出发每次走不超过k步所能吃到的最大量。 
有点难搞的是这里递归的顺序不好确定所以采用自顶向下的记忆化搜索的方式不用担心后效性因为每次走到新的位置的食物量都比当前的食物量要多 
因此这样定义子结构不具有后效性 
从起点开始搜索就行了 #include iostream
#include cstdio
#include cstring
using namespace std;
const int MAX  107;
int dp[MAX][MAX];
int a[MAX][MAX];
int n,k;
int dt[4][2]  {{0,1},{0,-1},{1,0},{-1,0}};
int dfs(int x,int y){if(dp[x][y]) return dp[x][y];dp[x][y]  a[x][y];for(int d  0;d  4;d){for(int i  1;i  k;i){int nx  x  dt[d][0]*i;int ny  y  dt[d][1]*i;if(nx  1  nx  n  ny  1  ny  n){if(a[x][y]  a[nx][ny]){dp[x][y]  max(dp[x][y],dfs(nx,ny)  a[x][y]);}}}}return dp[x][y];
}
int main(){while(scanf(%d%d,n,k) ! EOF  n  k  2){memset(dp,0,sizeof(dp));memset(a,0,sizeof(a));for(int i  1;i  n;i){for(int j  1;j  n;j){scanf(%d,a[i][j]);}}coutdfs(1,1)endl;}
}