poj 2948 Martian Mining (dp)-白红宇

poj 2948 Martian Mining (dp)

阅读量：5277 次

发布时间：2019-06-14

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

意：一个row*col的矩阵，每个格子内有两种矿yeyenum和bloggium，并且知道它们在每个格子内的数量是多少。如图所示，最北边有bloggium的收集站，最西边有 yeyenum 的收集站,

要你在这些格子上面安装向北或者向西的传送带(每个格子自能装一种)。问最多能采到多少矿(yeyenum+bloggium)？ poj <wbr>2948 <wbr>：Martian <wbr>Mining <wbr>(DP)

这道 dp 1A，完全自己写的，有点小兴奋，dp菜鸟在进步。。。。。。。，

首先开始想时

想了一个 dp 方程最后验证是错的；

后来自己有想了一下，得到了正确的状态方程

dp[i][j][0] 表示以 i，j 为右下角的矩形 i,j 这点选择向北的最大值

dp[i][j][1] 是选择向西的最大值

ans = max(dp[n][m][0],dp[n][m][1]);

状态转移：

dp[i][j][0] = 第 j 列求和 + max(dp[i][j - 1][0],dp[i][j - 1][1]);

dp[i][j][1] = 第 i 行求和 + max(dp[i - 1][j][0],dp[i - 1][j][1]);

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
             9 #define Min(a,b) a>b?b:a10 #define Max(a,b) a>b?a:b11 #define CL(a,num) memset(a,num,sizeof(a));12 #define inf 999999913 #define maxn 40014 #define mod (1000000000 + 7)15 #define eps 1e-616 #define ll long long17 using namespace std;18 ll dp[maxn][maxn][2];//0 上 1 左19 ll matu[maxn][maxn],matw[maxn][maxn];20 int main()21 {22 int n,m,i,j,t1;23 while(scanf("%d%d",&n,&m),n + m)24 {25 for(i = 1 ; i <= n; ++i)26 for(j = 1; j <= m ; ++j)27 {28 scanf("%lld",&matw[i][j]);29 }30 31 for(i = 1; i <= n ; ++i)32 {33 for(j = 1; j <= m ;++j)34 scanf("%lld",&matu[i][j]);35 }36 CL(dp,0);37 38 int sum = 0,k;39 for( i = 1 ; i <= n ;++i)40 {41 for( j = 1; j <= m; ++j )42 {43 sum = 0;44 for(k = i ; k >= 1; --k)sum += matu[k][j];45 46 dp[i][j][0] = sum + max(dp[i][j - 1][0],dp[i][j - 1][1]);47 48 sum = 0;49 for(k = j ;k >= 1; --k) sum += matw[i][k];50 51 dp[i][j][1] = sum + max(dp[i - 1][j][0],dp[i - 1][j][1]);52 53 }54 }55 56 printf("%lld\n",max(dp[n][m][0],dp[n][m][1]));57 58 59 }60 }

转载于:https://www.cnblogs.com/acSzz/archive/2012/08/11/2634007.html

你可能感兴趣的文章