acwing898.数字三角形

给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。

7      3   8    8   1   0  2   7   4   44   5   2   6   5

输入格式
第一行包含整数$n$，表示数字三角形的层数。

数据范围
$1\le n\le 500,-10000\le$三角形中的整数$\le 10000$

输入样例：

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

输出样例：

30

考虑做逆向dp，从下面往上看，$dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+s[i][j]$

#include<iostream>usingnamespacestd;#defineN510intdp[N][N],s[N][N];intn;intmain(){cin >>n;for(inti =1;i <=n;i ++)for(intj =1;j <=i;j ++)cin >>s[i][j];for(inti =n;i >=1;i --){for(intj =1;j <=i;j ++)dp[i][j]=max(dp[i +1][j],dp[i +1][j +1])+s[i][j];}cout <<dp[1][1]<<endl;}

acwing1015.摘花生

$dp[i][j]$：从$(1,1)$走到$(i,j)$的所有路线上的花生数量最大值
$dp[i][j]=max(dp[i][j-1],dp[i-1][j])+s[i][j]$

#include<iostream>usingnamespacestd;#defineN110intw[N][N];intdp[N][N];intt;intmain(){cin >>t;intr,c;while(t --){scanf("%d%d",&r,&c);for(inti =1;i <=r;i ++)for(intj =1;j <=c;j ++)scanf("%d",&w[i][j]);for(inti =1;i <=r;i ++)for(intj =1;j <=c;j ++)dp[i][j]=max(dp[i -1][j],dp[i][j -1])+w[i][j];printf("%dn",dp[r][c]);}return0;}

acwing1018.最低通行费

$dp[i][j]$：从$(1,1)$走到$(i,j)$的所有路线上的费用的最小值
$dp[i][j]=min(dp[i][j-1],dp[i-1][j])+s[i][j]$
摘花生问题考虑的是最大值，本问题考虑的是最小值，为了避免边界的影响，需要将dp所有位置上的值初始化为正无穷。
$dp[k][i][j]=max(dp[k-1][i][j],dp[k-1][i-1][j],dp[k-1][i][j-1],dp[k-1][i-1][j-1])+t$
即$dp[k][i][j]$的路线是每条路线从上面或者左面到达的，组合数量$2\ast 2=4$。

输出格式
输出一个整数，表示最大的路径数字和。

#include<iostream>#include<cstring>usingnamespacestd;#defineN110intn;intw[N][N];intdp[N][N];intmain(){cin >>n;for(inti =1;i <=n;i ++)for(intj =1;j <=n;j ++)scanf("%d",&w[i][j]);memset(dp,0x3f,sizeofdp);dp[1][1]=w[1][1];for(inti =1;i <=n;i ++)for(intj =1;j <=n;j ++){dp[i][j]=min(dp[i][j],dp[i -1][j]+w[i][j]);dp[i][j]=min(dp[i][j],dp[i][j -1]+w[i][j]);}cout <<dp[n][n];return0;}

acwing1027.方格取数
$dp[k][i][j]$:两条路同时走，步数为k，第一条路在纵向上走到i，第二条路在纵向上走到j时的所有路线上数值和的最大值。

接下来$n$行，每行包含若干整数，其中第 $i$行表示数字三角形第$i$层包含的整数。

#include<iostream>usingnamespacestd;#defineN20intdp[N +N][N][N];ints[N][N];intn;intmain(){cin >>n;intx,y,k;while(cin >>x >>y >>k,x ||y ||k)s[x][y]=k;for(inti =2;i <=n *n;i ++){for(intj =1;j <=n;j ++){for(intk =1;k <=n;k ++){intj1 =i -j,j2 =i -k;intt =s[j][j1];if(j !=k)t +=s[k][j2];if(j1 >=1&&j1 <=n &&j2 >=1&&j2 <=n){dp[i][j][k]=max(dp[i][j][k],dp[i -1][j -1][k -1]+t);dp[i][j][k]=max(dp[i][j][k],dp[i -1][j][k -1]+t);dp[i][j][k]=max(dp[i][j][k],dp[i -1][j -1][k]+t);dp[i][j][k]=max(dp[i][j][k],dp[i -1][j][k]+t);}}}}printf("%d",dp[n *2][n][n]);return0;}