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的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。