kuangbin专题十二 HDU1078 FatMouse and Cheese ）(dp + dfs 记忆化搜索)-白红宇

kuangbin专题十二 HDU1078 FatMouse and Cheese ）(dp + dfs 记忆化搜索)

阅读量：6756 次

发布时间：2019-06-26

本文共 3422 字，大约阅读时间需要 11 分钟。

FatMouse and Cheese

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 14253 Accepted Submission(s): 6035

Problem Description

FatMouse has stored some cheese in a city. The city can be considered as a square grid of dimension n: each grid location is labelled (p,q) where 0 <= p < n and 0 <= q < n. At each grid location Fatmouse has hid between 0 and 100 blocks of cheese in a hole. Now he's going to enjoy his favorite food.

FatMouse begins by standing at location (0,0). He eats up the cheese where he stands and then runs either horizontally or vertically to another location. The problem is that there is a super Cat named Top Killer sitting near his hole, so each time he can run at most k locations to get into the hole before being caught by Top Killer. What is worse -- after eating up the cheese at one location, FatMouse gets fatter. So in order to gain enough energy for his next run, he has to run to a location which have more blocks of cheese than those that were at the current hole.

Given n, k, and the number of blocks of cheese at each grid location, compute the maximum amount of cheese FatMouse can eat before being unable to move.

Input

There are several test cases. Each test case consists of

a line containing two integers between 1 and 100: n and k

n lines, each with n numbers: the first line contains the number of blocks of cheese at locations (0,0) (0,1) ... (0,n-1); the next line contains the number of blocks of cheese at locations (1,0), (1,1), ... (1,n-1), and so on.

The input ends with a pair of -1's.

Output

For each test case output in a line the single integer giving the number of blocks of cheese collected.

Sample Input

3 1 1 2 5 10 11 6 12 12 7 -1 -1

Sample Output

题目大意：和滑雪比较类似，只是多了一个最多k步的限制。dp + dfs即可

记忆化搜索。dfs一个点，求k步之内的最大值。还是对搜索发怵！！！！

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             10 #include 
              
               11 #include 
               
                12 #include 
                
                 13 #include 
                 
                  14 using namespace std;15 #define mem(a,b) memset((a),(b),sizeof(a))16 #define mp make_pair17 #define pb push_back18 #define fi first19 #define se second20 #define sz(x) (int)x.size()21 #define all(x) x.begin(),x.end()22 typedef long long ll;23 const int inf = 0x3f3f3f3f;24 const ll INF =0x3f3f3f3f3f3f3f3f;25 const double pi = acos(-1.0);26 const double eps = 1e-5;27 const ll mod = 1e9+7;28 //head29 const int maxn = 105;30 int dp[maxn][maxn], a[maxn][maxn];31 int des[4][2] = {-1, 0, 0, 1, 1, 0, 0, -1};//4个方向32 int n, k;33 34 bool check(int x, int y) { //越界35 if(x < 0 || x >= n || y < 0 || y >= n)36 return false;37 return true;38 }39 40 int dfs(int x, int y) {41 int ans = 0;//记录最大值42 if(dp[x][y] == 0) {43 for(int i = 1; i <= k; i++) { //k步44 for(int j = 0; j < 4; j++) { //4个方向45 int newx = x + des[j][0] * i;//走k步！！太酷了46 int newy = y + des[j][1] * i;47 if(check(newx, newy)) {48 if(a[newx][newy] > a[x][y])49 ans = max(ans, dfs(newx, newy));//最大值50 }51 }52 }53 dp[x][y] = ans + a[x][y];//更新dp[x][y]54 } 55 return dp[x][y];56 }57 58 int main() {59 while(~scanf("%d%d", &n, &k)) {60 if(n == -1)61 break;62 mem(dp, 0);63 for(int i = 0; i < n; i++) {64 for(int j = 0; j < n; j++) {65 scanf("%d", &a[i][j]);66 }67 }68 cout << dfs(0, 0) << endl;//dfs69 }70 }

转载于:https://www.cnblogs.com/ACMerszl/p/9572924.html

你可能感兴趣的文章