lightoj1036_记忆化搜索-白红宇

lightoj1036_记忆化搜索

阅读量：4695 次

发布时间：2019-06-09

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

题意：给出一个n*m的地图，每个位置含有xi的金矿和yi的银矿。金矿都要运到地图的西边，银矿都要运到地图的南边。

每个位置可以建铁路，但是只能建东-西或者南-北中的一个，也就是所有铁路不能交叉，而且矿石不能倒车，也就是必须沿直线运到目的地。

求一种建铁路的方式使得最后得到的矿石最多？输出矿石数量。

思路：问题的本质在于，对于一个格子，要么是向左要么向上：

（1）若一旦确定取该格子的矿金矿，则该格子左侧的都要取金矿；

（2）若一旦确定取该格子的矿银矿，则该格子上侧的都要取银矿；

看透这一步，就可以DP了。。。其实直接递推也挺简单的。。。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             
              10 #include 
              
               11 #include 
               12 using namespace std;13 #define INF 0x3f3f3f3f14 typedef long long LL;15 16 int a[510][510], b[510][510];17 int dp[510][510];18 struct node19 {20 int c;21 }suma[510][510], sumb[550][550];22 int dfs(int n, int m)23 {24 if(n == 1 && m == 1)25 return max(a[1][1], b[1][1]);26 if(n < 1 || m < 0)27 return 0;28 if(dp[n][m] != -1)29 return dp[n][m];30 int sum = 0;31 sum = max(suma[n][m].c + dfs(n-1, m), sumb[n][m].c + dfs(n, m-1));32 dp[n][m] = sum;33 return sum;34 }35 int main()36 {37 int t, n, m;38 scanf("%d", &t);39 for(int ca = 1; ca <= t; ca++)40 {41 memset(suma, 0, sizeof(suma));42 memset(sumb, 0, sizeof(sumb));43 scanf("%d %d", &n, &m);44 for(int i = 1; i <= n; i++)45 {46 for(int j = 1; j <= m; j++)47 {48 scanf("%d", &a[i][j]);49 suma[i][j].c = suma[i][j-1].c + a[i][j];50 }51 }52 for(int i = 1; i <= n; i++)53 {54 for(int j = 1; j <= m; j++)55 {56 scanf("%d", &b[i][j]);57 sumb[i][j].c = sumb[i-1][j].c + b[i][j];58 }59 }60 memset(dp, -1, sizeof(dp));61 int res = dfs(n, m);62 printf("Case %d: %d\n", ca, res);63 }64 return 0;65 }

转载于:https://www.cnblogs.com/luomi/p/5967058.html

你可能感兴趣的文章

(网页)the server responded with a status of 403 (Forbidden)