51Nod 1084 矩阵取数问题 V2 双线程DP 滚动数组优化-白红宇的个人博客

51Nod 1084 矩阵取数问题 V2 双线程DP 滚动数组优化

发布日期：2021-05-09 04:21:29 浏览次数：11 分类：博客文章

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

基准时间限制：2 秒空间限制：131072 KB

一个M*N矩阵中有不同的正整数，经过这个格子，就能获得相应价值的奖励，先从左上走到右下，再从右下走到左上。第1遍时只能向下和向右走，第2遍时只能向上和向左走。两次如果经过同一个格子，则该格子的奖励只计算一次，求能够获得的最大价值。

例如：3 * 3的方格。

1 3 3

2 1 3

2 2 1

能够获得的最大价值为：17。1 -> 3 -> 3 -> 3 -> 1 -> 2 -> 2 -> 2 -> 1。其中起点和终点的奖励只计算1次。

Input

第1行：2个数M N，中间用空格分隔，为矩阵的大小。(2 <= M, N <= 200)第2 - N + 1行：每行M个数，中间用空格隔开，对应格子中奖励的价值。(1 <= A[i,j] <= 10000)

Output

输出能够获得的最大价值。

Input示例

3 31 3 32 1 32 2 1

Output示例

思路：双线DP，看成两个人一起从（1,1）到（N，M），走的路径不能相同。

方法1：按照路径长度考虑，路径总长度：tot=x+y-1，dp[tot][x1][x2]，两个人的横坐标x1，x2

1 #include 
        
          2 using namespace std; 3 int ans[205][205],dp[405][205][205]; 4 int main() { 5     int M,N; 6     scanf("%d %d",&M,&N); 7     for(int i=1;i<=N;++i) 8         for(int j=1;j<=M;++j)  9             scanf("%d",&ans[i][j]);10     memset(dp,0,sizeof(dp));11     for(int tot=1;tot<=N+M-1;++tot)//路径长度12         for(int i=1;i<=N&&(1<=tot+1-i);++i)13             for(int j=1;j<=N&&(1<=tot+1-j);++j) {14                 dp[tot][i][j]=max(dp[tot][i][j],dp[tot-1][i-1][j-1]);15                 dp[tot][i][j]=max(dp[tot][i][j],dp[tot-1][i-1][j]);16                 dp[tot][i][j]=max(dp[tot][i][j],dp[tot-1][i][j-1]);17                 dp[tot][i][j]=max(dp[tot][i][j],dp[tot-1][i][j])+ans[i][tot+1-i]+ans[j][tot+1-j];18                 if(i==j) dp[tot][i][j]-=ans[i][tot+1-i];19             }20     printf("%d\n",dp[N+M-1][N][N]);21     return 0;22 }

View Code

方法2：按照走到走了几步，总的步数：tot=x+y-2

1 #include 
        
          2 using namespace std; 3 int ans[205][205],dp[405][205][205]; 4 int main() { 5     int M,N; 6     scanf("%d %d",&M,&N); 7     for(int i=1;i<=N;++i) 8         for(int j=1;j<=M;++j)  9             scanf("%d",&ans[i][j]);10     memset(dp,0,sizeof(dp));11     dp[0][1][1]=ans[1][1];//一步都没走12     for(int tot=1;tot<=N+M-2;++tot)//走了几步13         for(int i=1;i<=N&&(i-1<=tot);++i)14             for(int j=1;j<=N&&(j-1<=tot);++j) {15                 dp[tot][i][j]=max(dp[tot][i][j],dp[tot-1][i-1][j-1]);16                 dp[tot][i][j]=max(dp[tot][i][j],dp[tot-1][i-1][j]);17                 dp[tot][i][j]=max(dp[tot][i][j],dp[tot-1][i][j-1]);18                 dp[tot][i][j]=max(dp[tot][i][j],dp[tot-1][i][j])+ans[i][tot+2-i]+ans[j][tot+2-j];19                 if(i==j) dp[tot][i][j]-=ans[i][tot+2-i];20             }21     printf("%d\n",dp[N+M-2][N][N]);22     return 0;23 }

View Code

方法3：对方法2的优化，滚动数组

1 #include 
        
          2 #include 
         
           3 int ans[201][201],dp[2][201][201]; 4 int max(int a, int b) {if(a>=b) return a;return b;} 5 int main() { 6     int M,N; 7     scanf("%d %d",&M,&N); 8     for(int i=1;i<=N;++i) 9         for(int j=1;j<=M;++j) 10             scanf("%d",&ans[i][j]);11     memset(dp,0,sizeof(dp));12     dp[0][1][1]=ans[1][1];//一步都没走13     int dir=0;14     //tot->走了几步15     for(int tot=1;tot<=N+M-2;++tot) {16         dir=1-dir;17         for(int i=1;i<=N&&(i-1<=tot);++i)18             for(int j=1;j<=N&&(j-1<=tot);++j) {19                 dp[dir][i][j]=max(dp[dir][i][j],dp[1-dir][i-1][j-1]);20                 dp[dir][i][j]=max(dp[dir][i][j],dp[1-dir][i-1][j]);21                 dp[dir][i][j]=max(dp[dir][i][j],dp[1-dir][i][j-1]);22                 dp[dir][i][j]=max(dp[dir][i][j],dp[1-dir][i][j])+ans[i][tot+2-i]+ans[j][tot+2-j];23                 if(i==j) dp[dir][i][j]-=ans[i][tot+2-i];24             }25     }26     printf("%d\n",dp[dir][N][N]);27     return 0;28 }

View Code

上一篇：HDU 2686 Matrix 多线程dp

下一篇：codeforces 887A Div. 64 思维模拟

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章