动态规划训练21 [FatMouse and Cheese HDU - 1078 ]

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]);}}cout<<dfs(1,1)<<endl;} }

总结

以上是生活随笔为你收集整理的动态规划训练21 [FatMouse and Cheese HDU - 1078 ]的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。