#双线dp

• 双线表示同时有两种状态，且会相互影响

题意

• 给定M*N的地图，每个点有val，每个点只能走一次
• 从左上走到右下再走回左上，且向下的过程只能向下向右，向上的过程只能向上向左
• 走完最多获得的val是多少

思路

• 思路一：严格按照一圈走无法完成，走下去的过程走过的格子会影响走上去的过程的路径，不妨同时完成，又走上去和走下去完全相同，不妨设两个人同时从起点出发，走到终点，用四维的dp来记录两个人的位置，当两个人重叠的时候就把dp记为无穷小
• 思路二：可以发现，两个人走的步数是相同的，我们只用记录来表示走了k步，第一个人向下走了i步，第二个人向下走了j步，同样地，当i=j时记为无穷小

代码

#include<bits/stdc++.h>

using namespace std;

/**
 * dp[i][j][k][l]第一个人在(i,j)第二个在(k,l)和最大
 * dp[i][j][k][l]=dp四个方向
 */
int dp[60][60][60][60];
int a[60][60];
int n,m;

int judge(int i,int j,int k,int l){
    if(i==1&&j==1&&k==1&&l==1)return 0;
    if(i==m&&j==n&&k==m&&l==n)return 0;
    return 1;
}
int main(){
    cin >> m >> n;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            cin >> a[i][j];
        }
    }
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=m;k++){
                for(int l=1;l<=n;l++){
                    if(i==k&&j==l&&judge(i,j,k,l)) dp[i][j][k][l]=-0x3f3f3f3f;
                    else dp[i][j][k][l]=max(dp[i-1][j][k-1][l],max(dp[i-1][j][k][l-1],max(dp[i][j-1][k-1][l],dp[i][j-1][k][l-1])))+a[i][j]+a[k][l];

                }
            }
        }
    }
    cout << dp[m][n][m][n] <<endl;
    return 0;
}