动态规划——数字三角形模型
数字三角形模型
母题 ： 数字三角形
思路
集合 f [i] [j] 表示所有从起点走到(i,j)的路径
属性 f [i] [j] 存的数是集合中所有路径和的最大值
状态计算：对于每一条从起点到 ( i , j ) 的路径，其要么是从左上方来的，要么是从右上方来的。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n;
int a[510][510];
int f[510][510];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++) cin>>a[i][j];
for(int i=0;i<=n;i++)
for(int j=0;j<=i+1;j++) f[i][j]=-1e9;
f[1][1]=a[1][1];
for(int i=2;i<=n;i++)
for(int j=1;j<=i;j++)
f[i][j]=max(f[i-1][j],f[i-1][j-1])+a[i][j];
int mmax=-1e9;
for(int i=1;i<=n;i++) mmax=max(mmax,f[n][i]);
cout<<mmax<<endl;
return 0;
}
子题1 ： 摘花生
思路
基本和母题的思路一致，转移方程一致
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+10;
int f[N][N];
int w[N][N];
void solve()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
cin>>w[i][j];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
f[i][j]=max(f[i-1][j],f[i][j-1])+w[i][j];
}
cout<<f[n][m]<<endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T=1;
cin>>T;
while(T--)
{
solve();
}
return 0;
}
子题2 ： 最低通行费
思路
因为必须在(2*N-1)个单位时间穿越过来，所以只能向右或向左移动
集合 f [i] [j] 表示走到第i行第j列的所有方案
属性 走过路线的总价值最小值Min
转移方程
从左面走过来 从右面走过来
f [i] [j] = f [i] [j-1] +w f [i] [j] = f [i-1] [j] +w
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+10;
const int inf = 1e9;
int w[N][N];
int f[N][N];
void solve()
{
int n;
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
cin>>w[i][j];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==1&&j==1) f[i][j]=w[i][j];
else
{
f[i][j]=inf;
if(i>1) f[i][j]=min(f[i][j],f[i-1][j]+w[i][j]);
if(j>1) f[i][j]=min(f[i][j],f[i][j-1]+w[i][j]);
}
}
}
cout<<f[n][n]<<endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T=1;
// cin>>T;
while(T--)
{
solve();
}
return 0;
}
子题3 ：方格取数
思路
和之前的题不同是本题需要走两边
如果只走一次的话，求从起点到终点的最大权值和应该为：f[i] [j] = max(f[i-1] [j], f[i][j-1])+w[i] [j]; 即f[i][j]表示从起点走到（i，j）的最大权值和，
而本题是从起点走两次走到终点的最大权值和，即状态表示为：f[i1] [j1] [i2] [j2]；这里，我们考虑假设两条路线是同时走的，则表示为：所有从起点（1，1）（1，1）出发，然后分别走到（i1，j1），（i2，j2）的最大权值和
我们可以进行 三维优化
状态表示 f [k] [x1] [x2]
集合 同时走K步，所有从（1，1），（1，1）走到 (x1,y1),(x2,y2) 获得花生的数目
属性 Max
状态计算 左 左 f [k-1] [x1-1] [x2-1]
左 上 f [k-1] [x1-1] [x2]
上 左 f [k-1] [x1] [x2-1]
上 上 f [k-1] [x1] [x2]
特判 两个点是否重合 即 x1==x2 如果重合只加w [x1] [j1] 如果不重合加 w [x1] [j1] +w [x2] [j2]
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=15;
int w[N][N];
int f[N*2][N][N];
void solve()
{
int n; cin>>n;
int a,b,c;
while(cin>>a>>b>>c,a||b||c) w[a][b]=c;
for(int k=2;k<=n*2;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*2][n][n];
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T=1;
// cin>>T;
while(T--)
{
solve();
}
return 0;
}
子题4 ： 传纸条
思路
可以思考成和方格取数 相同的代码逻辑，一个从上向下走，一个从下向上走，可以理解为两条路从上向下走，加上其限制条件
状态表示 f [k] [x1] [x2]
集合 同时走K步，所有从（1，1），（1，1）走到 (x1,y1),(x2,y2) 得到权值的最大值
状态计算
左 左 f [k-1] [x1-1] [x2-1]
左 上 f [k-1] [x1-1] [x2]
上 左 f [k-1] [x1] [x2-1]
上 上 f [k-1] [x1] [x2]
注意 不能走到一个格子里 (和方格取数不同的地方) ，因为最优解一定不会相交，一定可以绕开这个点向其他地方走
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=55;
int w[N][N];
int f[N*2][N][N]; //表示两条路径分别到达(i,k-i),(j,k-j);
void solve()
{
int n,m; cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
cin>>w[i][j];
}
for(int k=2;k<=n+m;k++){
for(int i=1;i<k;i++){
for(int j=1;j<k;j++){
int &v=f[k][i][j];
int tmp=w[i][k-i];
if(i!=j) tmp+=w[j][k-j];
v=max(v,f[k-1][i-1][j]);
v=max(v,f[k-1][i-1][j-1]);
v=max(v,f[k-1][i][j-1]);
v=max(v,f[k-1][i][j]);
v+=tmp;
}
}
}
cout<<f[n+m][n][n];
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T=1;
// cin>>T;
while(T--)
{
solve();
}
return 0;
}