首页 > 代码库 > HDU 1078 FatMouse and Cheese
HDU 1078 FatMouse and Cheese
记忆化搜索，$dp$。
每一个点走到的最长距离是固定的，也就是只会算一次，那么记忆化一下即可，也可以按值从小到大排序之后进行$dp$。
记忆化搜索：
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int T,n,k;int v[110][110];int dp[110][110];int f[110][110];int dir[4][2]={ {1,0}, {-1,0}, {0,1}, {0,-1}};int ok(int x,int y){ if(x>=0&&x<n&&y>=0&&y<n) return 1; return 0;}int dfs(int x,int y){ if(f[x][y]) return dp[x][y]; int mx = 0; for(int d=0;d<4;d++) { for(int p=1;p<=k;p++) { int tx = x+p*dir[d][0]; int ty = y+p*dir[d][1]; if(!ok(tx,ty)) continue; if(v[x][y]>=v[tx][ty]) continue; mx = max(mx,dfs(tx,ty)); } } f[x][y]=1; dp[x][y] = mx+v[x][y]; return dp[x][y];}int main(){ while(~scanf("%d%d",&n,&k)) { if(n==-1&&k==-1) break; memset(dp,0,sizeof dp); memset(f,0,sizeof f); for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { scanf("%d",&v[i][j]); } } printf("%d\n",dfs(0,0)); } return 0;}
$dp$：
#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<map>#include<queue>#include<string>#include<iostream>using namespace std;int n,k;int v[110][110];struct X{ int r,c,val;}s[10010];int sz;int dp[110][110];int dir[4][2]={ {1,0}, {-1,0}, {0,1}, {0,-1}};bool cmp(X a,X b){ return a.val<b.val;}bool ok(int x,int y){ if(x>=0&&x<n&&y>=0&&y<n) return 1; return 0;}int main(){ while(~scanf("%d%d",&n,&k)) { if(n==-1&&k==-1) break; sz=0; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { scanf("%d",&v[i][j]); s[sz].r = i; s[sz].c = j; s[sz].val = v[i][j]; sz++; } } sort(s,s+sz,cmp); memset(dp,0,sizeof dp); dp[0][0] = v[0][0]; int ans=0; for(int i=0;i<sz;i++) { if(dp[s[i].r][s[i].c]==0&&(s[i].r!=0||s[i].c!=0)) continue; // printf("!!! %d %d \n",s[i].r,s[i].c); for(int d=0;d<4;d++) { for(int p=1;p<=k;p++) { int tx = s[i].r+p*dir[d][0]; int ty = s[i].c+p*dir[d][1]; if(!ok(tx,ty)) continue; if(v[s[i].r][s[i].c]>=v[tx][ty]) continue; dp[tx][ty] = max(dp[tx][ty],dp[s[i].r][s[i].c] + v[tx][ty]); } } } for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { ans=max(ans,dp[i][j]); } } printf("%d\n",ans); } return 0;}
HDU 1078 FatMouse and Cheese
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。