Acwing 1027.方格取数

题目链接

算法1

(数字三角性模型)

这道题是摘花生 题目的延申

摘花生：走一条路

这道题与摘花生题的区别在于走的路数，该题走两条路，而且是两条路同时走的思想。

那么按照摘花生的题的思路，能否两条路各自取最大值呢？

答案是不行。

因为第一次摘花生，第一次的最优解已经影响到第二次的最优解了。两次分开走并不是全局最优的。只能dp同时走才可以找到全局最优方案。

例：

0  1  0
2  2  2
1  0  0

如果分两次，第一次最优肯定是把三个2取到然后结束，第二次就只能取一个1。
如果同时来，那么是可以把所有的数都取下的。

上述例子来源于评论区

1.状态定义：

f[i1][j1][i2][j2]：从(1,1),(1,1)分别走到(i1,j1),(i2,j2)的路径上的最大值

注意：同一个格子只能选择一次

我们可以发现两个路径走过的总步数是一样的。

因此只有在$i_1 + j_1 == i_2 + j_2$时，两条路径的格子才可能重合

可能重合的意思就是它不仅包含了重合的情况，而且包含了不重复的情况

这样我们可以从四维，降到三维

状态定义：f[k][i1][i2] : 表示所有从(1,1),(1,1)点出发，分别到达(i1,k-i1),(i2,k-i2)的路径上的最大值

其中k表示两条路线，当前走到的格子的横纵坐标之和，即 k: i1+ j1 = i2 + j2;

2.状态计算：

for(int k = 2; k <= n + n; k++){
    for(int i1 = 1; i1 <= n; i1++){
        for(int i2 = 1; i2 <= n; i2++)
        {
            int j1 = k - i1, j2 = k - i2;
            
            if(j1 >= 1 && j1 <= n && j2 >= 1 && j2 <= n)
            {
               //如果是同一个格子只加一次即可
               int t = w[i1][j1];   
               if(i1 != i2) t += w[i2][j2];
               
               int &x = f[k][i1][i2];
               
               //1.两条路都是从上方过来的
               x = max(x,f[k-1][i1-1][i2-1] + t);
               
               //2.第一条路是从左过来，第二条路是从上方过来的
               x = max(x,f[k-1][i1][i2-1] + t);
               
               //3.第一条路：从上来的，第二条路：从左来的
               x = max(x,f[k-1][i1-1][i2-1] + t);
               
               //4.两条路都是从左过来的
               x = max(x,f[k-1][i1][i2] + t);
            } 
        }
    }
     最终答案：f[n+n][n][n];
}

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 15;

int n;
int w[N][N];
int f[N*2][N][N];

//两个横纵坐标最大值和为 N + N;


int main(){
    
    cin >> n;
    int a,b,c;
    while(cin >> a >> b >> c,a || b || c) w[a][b] = c;
    
    for(int k = 2 ; k <= n + n; k ++){
        for(int i1 = 1; i1 <= n; i1++){
            for(int i2 = 1; i2 <= n; i2++){
               
               //第一步先求纵坐标
               int j1 = k - i1, j2 = k - i2;
               
               //只有在边界内才能算出答案
               if(j1 >=1 && j1 <= n && j2 >= 1 && j2 <= n)
               {
                  int t = w[i1][j1]; //如果处在同一个格子只算一次
                  
                  if(i1 != i2) //不在同一个格子的时候
                  t += w[i2][j2];
                  
                  int &x = f[k][i1][i2];
                  x = max(x,f[k-1][i1-1][i2-1] + t);
                  x = max(x,f[k-1][i1-1][i2] + t);
                  x = max(x,f[k-1][i1][i2-1] + t);
                  x = max(x,f[k-1][i1][i2] + t);
                  
               }
            }
        }
    }
    
    cout << f[n+n][n][n];
    
    return 0;
}