[Acwing] 算法提高课汇总一 动态规划- 数字三角形模型

数字三角形模型

1. 摘花生

就是最基础的数字三角形模型

状态表示 :
f [ i ] [ j ] f[i][j] f[i][j]表示当前 ( i , j ) (i,j) (i,j)的最大价值

状态转移 :
f [ i ] [ j ] = m a x ( f [ i − 1 ] [ j ] , f [ i ] [ j − 1 ] ) f[i][j] = max(f[i-1][j],f[i][j-1]) f[i][j]=max(f[i−1][j],f[i][j−1])

2.最低通行费

这个题还是最基础的数字三角形模型

只是变向的问了

对于一个 N × N N×N N×N的网格,限定 2 N − 1 2N-1 2N−1步走出去

根据曼哈顿距离,我们可以知道如果只往下和右走,那么所需的距离正好就是 2 N − 1 2N-1 2N−1

因此问题又回到了那个模板的问题

3.方格取数

题意 :
对于方格 ( i , j ) (i,j) (i,j)都赋予一个 w i , j w_{i,j} wi,j​

试问类似摘花生那种做法,做两次的最大值

拿完之后该点的权值为0

思路 :
如果分开走的话,那么第一次走完之后会有后效性影响第二次拿的价值,所以必须同时走

状态表示 :
f [ i 1 ] [ j 1 ] [ i 2 ] [ j 2 ] f[i_1][j_1][i_2][j_2] f[i1​][j1​][i2​][j2​]表示同时分别走到 从 ( 1 , 1 ) 开 始 走 到 ( i 1 , j 1 ) ( i 2 , j 2 ) 从(1,1)开始走到(i_1,j_1)(i_2,j_2) 从(1,1)开始走到(i1​,j1​)(i2​,j2​)的路径的集合

状态计算 :
f [ i 1 ] [ j 1 ] [ i 2 ] [ j 2 ] = m a x ( f[i_1][j_1][i_2][j_2]=max( f[i1​][j1​][i2​][j2​]=max(

f [ i 1 − 1 ] [ j 1 ] [ i 2 − 1 ] [ j 2 ] − 从 上 面 转 移 f[i_1-1][j_1][i_2-1][j_2] -从上面转移 f[i1​−1][j1​][i2​−1][j2​]−从上面转移
f [ i 1 ] [ j 1 − 1 ] [ i 2 − 1 ] [ j 2 ] − 从 左 边 和 上 面 转 移 f[i_1][j_1-1][i_2-1][j_2] -从左边和上面转移 f[i1​][j1​−1][i2​−1][j2​]−从左边和上面转移
f [ i 1 ] [ j 1 − 1 ] [ i 2 ] [ j 2 − 1 ] − 从 左 边 转 移 f[i_1][j_1-1][i_2][j_2-1] -从左边转移 f[i1​][j1​−1][i2​][j2​−1]−从左边转移
f [ i 1 − 1 ] [ j 1 ] [ i 2 ] [ j 1 − 1 ] − 从 上 面 和 左 边 转 移 ) f[i_1-1][j_1][i_2][j_1-1] - 从上面和左边转移) f[i1​−1][j1​][i2​][j1​−1]−从上面和左边转移)

当然因为拿完就置 0 0 0的存在,我们需要考虑 ( i 1 , j 1 ) ( i 2 , j 2 ) (i_1,j_1)(i_2,j_2) (i1​,j1​)(i2​,j2​)是否是相同的格子

因此我们可以做一个优化

我们令 k = i 1 + j 1 = i 2 + j 2 k=i_1+j_1=i_2+j_2 k=i1​+j1​=i2​+j2​

我们只需要 n ∗ 2 n*2 n∗2的枚举 k k k以及枚举 i 1 i_1 i1​, i 2 i_2 i2​然后通过计算出来 j 1 j_1 j1​ j 2 j_2 j2​即可

最后判断是否相同

const int N = 15;

int n;
int w[N][N], f[N*2][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