历届试题地宫取宝记忆化搜索-白红宇

历届试题地宫取宝记忆化搜索

阅读量：5272 次

发布时间：2019-06-14

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

思路：状态d(x, y, k, max_num)表示当前已经走到坐标(x, y)，拿到了k个宝物，宝物的最大值是max_num。

1、如果当前点宝物的值等于max_num，那么他可以选择拿取当前宝物，那么下个状态就是d(x, y-1, k-1, w)，d(x-1, y, k-1, w)，0 <= w < max_num；

2、不管当前宝物是什么情况，都不拿当前宝物，一直向下搜索，那么下个状态就是d(x, y-1, k, max_num)，d(x-1, y, k-1, max_num)；

注意：第一种状态转移，可能会出现k==0的情况，此时可能会转移到多个k==0，max_num会有多个值，就存在重复计算，应该特殊处理一下。

状态转移：

for(int j = 0; j < 2; ++j) {		int px = x + dx[j], py = y + dy[j];		if(px < 0 || py < 0) continue;		//拿取当前点宝物		if(a[x][y] == max_num)  {			if(cnt > 1) for(int i = 0; i < max_num; ++i) {				ans += dfs(px, py, cnt-1, i); 				ans %= mod;			}			else if(cnt == 1) ans += dfs(px, py, 0, 0);		}		//不拿取当前宝物		ans += dfs(px, py, cnt, max_num); 		ans %= mod;	}	return ans;

边界

if(x == 0 && y == 0) {		if(cnt == 0) return ans = 1;		if(cnt == 1 && max_num == a[x][y]) return ans = 1;		return ans = 0;	}

AC代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              #include 
              
               #include 
               
                using namespace std;#pragma comment(linker, "/STACK:1024000000,1024000000") #define eps 1e-10#define inf 0x3f3f3f3f#define PI pair
                
                  typedef long long LL;const int maxn = 50 + 2, mod = 1000000007;int d[maxn][maxn][14][14], a[maxn][maxn];int n, m, k;const int dx[] = {0, -1};const int dy[] = {-1, 0};int dfs(int x, int y, int cnt, int max_num) { if(cnt < 0) return 0; int &ans = d[x][y][cnt][max_num]; if(ans != -1) return ans; ans = 0; //边界 if(x == 0 && y == 0) { if(cnt == 0) return ans = 1; if(cnt == 1 && max_num == a[x][y]) return ans = 1; return ans = 0; } for(int j = 0; j < 2; ++j) { int px = x + dx[j], py = y + dy[j]; if(px < 0 || py < 0) continue; //拿取当前点宝物 if(a[x][y] == max_num) { if(cnt > 1) for(int i = 0; i < max_num; ++i) { ans += dfs(px, py, cnt-1, i); ans %= mod; } else if(cnt == 1) ans += dfs(px, py, 0, 0); } //不拿取当前宝物 ans += dfs(px, py, cnt, max_num); ans %= mod; } return ans;}int main() { while(scanf("%d%d%d", &n, &m, &k) == 3) { memset(d, -1, sizeof(d)); for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j) scanf("%d", &a[i][j]); int ans = 0; for(int i = 0; i < 13; ++i) { ans += dfs(n-1, m-1, k, i); ans %= mod; } printf("%d\n", ans); } return 0;}

如有不当之处欢迎指出！

转载于:https://www.cnblogs.com/flyawayl/p/8305370.html

你可能感兴趣的文章