当前位置：首页 > news >正文

动态规划——线性dp

news 来源：原创 2024/11/15 12:30:59

动态规划

$参考闫氏 d p 分析法$

方格取数

$f [i 1] [j 1] [i 2] [j 2] 表示（ 1, 1 ）到（ i 1, j 1 ）和（ 1, 1 ）到 (i 2, j 2) 和的最大值$
$利用最后一步不同的思想，找个集合可以由四种状态转移过来$
$分别是第一次到 (i 1, j 1) 的两种转移状态乘以 (i 2, j 2) 的两种转移状态$
$这个题还有个限制就是不可以重复取，第一次取了第二次就清零了$
$就相当于先确定 (i 1, j 1) 的位置然后推出所有 f [i 1] [j 1] [i 2] [j 2] 的值，如果不重复就是 w [i 1] [j 1] + w [i 2] [j 2] ，如果是重合的终点那么就只加一个$

四维代码

#include<bits/stdc++.h>

using namespace std;

const int N = 12;

int n, x, y, c;

int f[N][N][N][N];

int w[N][N];

int main(){
    
    cin >> n;
    
    while((cin >> x >> y >> c), (x && y && c)){
        w[x][y] = c;
    }
    
    for(int i1 = 1; i1 <= n; i1 ++)
    {
        for(int j1 = 1; j1 <= n; j1 ++)
        {
            for(int i2 = 1; i2 <= n; i2 ++)
            {
                for(int j2 = 1; j2 <= n; j2 ++)
                {
                    int &v = f[i1][j1][i2][j2];
                    v = f[i1-1][j1][i2-1][j2] + w[i1][j1];
                    v = max(f[i1][j1-1][i2-1][j2] + w[i1][j1], v);
                    v = max(f[i1-1][j1][i2][j2-1] + w[i1][j1], v);
                    v = max(f[i1][j1-1][i2][j2-1] + w[i1][j1], v);
                    if(i1 != i2 && j1 != j2)
                    {
                        v += w[i2][j2];
                    }
                }
            }
        }
    }
    cout << f[n][n][n][n];
    return 0;
    
}