FatMouse and Cheese
生活随笔
收集整理的这篇文章主要介绍了
FatMouse and Cheese
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
http://acm.hdu.edu.cn/showproblem.php?pid=1078
题解：记忆化搜索
这个题可以用深搜去做，从（0，0）点出发，两层for循环记录位置，外层代表四个方向，内层是走了多少步，走到一个位置如果数值比前一步大的话，加上数值继续dfs，每次返回时更新一下最大值。在两层for循环结束后，得到的maxx的值就是该点能得到的最多奶酪数，然后将maxx赋给book[x][y]记录一下这个点的最大奶酪数,这个题有一个剪枝，如果遇到一个点它被记录过了，那么直接用就行了，不用再搜索。最后返回到主函数加上（0，0）点对应的值就好了。
/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int using namespace std; typedef long long ll; //typedef __int128 lll; const int N=1000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k; ll ans,cnt,flag,temp; ll a[N][N]; int b[][2]={1,0,0,1,-1,0,0,-1}; ll c[N][N]; bool vis[N][N]; char str; void dfs(int x,int y){//printf("%d %d\n",x,y);if(c[x][y])return;c[x][y]=a[x][y];for(int i=0;i<4;i++){for(int j=1;j<=k;j++){int tx=x+b[i][0]*j;int ty=y+b[i][1]*j;if(tx<1||tx>n||ty<1||ty>n)break;if(a[x][y]<a[tx][ty]){dfs(tx,ty);c[x][y]=max(c[x][y],c[tx][ty]+a[x][y]);}}} }int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//;//scanf("%d",&t);while(~scanf("%d%d",&n,&k)){if(n==-1&&k==-1)break;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%lld",&a[i][j]);memset(c,0,sizeof(c));dfs(1,1);printf("%lld\n",c[1][1]);}//cout << "Hello world!" << endl;return 0; }
总结
以上是生活随笔为你收集整理的FatMouse and Cheese的全部内容，希望文章能够帮你解决所遇到的问题。
