数字三角形模型
求从左上角到右下角走一次的最大或最小值
有一个n*m的网格，每个网格都有一个数，给你规定可以走的方向和走的次数，求从左上角到右下角的最大或者最小值。
常规的一般是可以向下或者向右走，走一次之后求从左上角到右下角的最大值或者最小值，那么状态转移的方程就是：
f[i][j]=max(f[i][j],f[i-1][j]);
f[i][j]=max(f[i][j],f[i][j-1]);
从左上角到右下角走两次的最大值
例题：https://www.acwing.com/problem/content/1029/
题意：一个n*n的格子每个格子里都有一个数，从（1,1）到（n，n）走两条路径，走过的路径的格子里的数被拿走，每个格子里的数只能被拿一次，每次只能向下或者向右走，求走两条路径拿的数的和的最大值。
思路：
不能按第一条路最优第二条路最优的方式分开求，因为第一条路最优的时候第二条路不一定最优。那么就考虑两条路同时走。
f[i1][j1][i2][j2]：表示第一条路和第二条路同时走，第一条路从（1，1）走到(i1,j1)，第二条路从（1,1）走到(i2,j2)时，所有路径的最大值。
四重循环肯定会超时或者超内存，所以我们需要优化一维。
从（1,1）到（n，n）同时走，要么向下要么向右，实际上都是横坐标或者是纵坐标+1，那么两条路同时走到的格子，横纵坐标相加就是一个固定值。那么我们就用一维k来表示横纵坐标相加的值。
如何去处理同一个格子不能被重复选择的情况：
当i1+j1==i2+j2时，两条路的格子可能重合。
然而其实两个格子同时走的话，i1+j1恒等于i2+j2,因为要么两条路横坐标+1或者纵坐标+1，那么相加的和都是一样的。
那么我们就可以优化到三维：
f[k][i1][i2]：k表示i1+j1的和，也等于i2+j2的和，i1是从第一条路走到的点的横坐标，i2是从第二条路走到的点的纵坐标。
那么状态表示就是：两条路同时走，第一条路从（1,1）开始走到（i1，k-i1），第二条路从（1,1）开始走到（i2，k-i2）的最大值。
每个路线都可以向下走或者向右走，那么两条路线就有四种情况：
1.第一条向下，第二条向下：f[k-1][i1-1][i2-1]
2.第一条向下，第二条向右:f[k-1][i1-1][i2]
3.第一条向右，第二条向下:f[k-1][i1][i2-1]
4.第一条向右，第二条向右:f[k-1][i1][i2]
那么当走到(i1,j1)和（i2，j2）的时候，当两个格子在同一个地方那么就加一个格子，在不同地方就都加上。
#include<bits/stdc++.h>
using namespace std;
const int N=20;
int f[N][N][N];
int a[N][N];
int n;
int main(){
cin>>n;
int i,j,k;
while(cin>>i>>j>>k,i||j||k){
a[i][j]=k;
}
memset(f,-0x3f,sizeof f);
f[2][1][1]=a[1][1];
for(int k=2;k<=n*2;k++){
for(int i1=1;i1<=n;i1++){
for(int i2=1;i2<=n;i2++){
int &x=f[k][i1][i2];
int j1=k-i1,j2=k-i2;
int t=a[i1][j1];
if(i1!=i2) t+=a[i2][j2];
x=max(x,f[k-1][i1][i2]+t);
x=max(x,f[k-1][i1-1][i2-1]+t);
x=max(x,f[k-1][i1][i2-1]+t);
x=max(x,f[k-1][i1-1][i2]+t);
}
}
}
cout<<f[n*2][n][n]<<endl;
return 0;
}
变形
例题：https://www.acwing.com/problem/content/277/
题意：一个人从左上角到右下角，另一个人从右下角到左上角，每个格子都有一个数值，但是每个格子只能被走一次，不能被两个人走。第一个人只能往下或往右，第二个人只能向上或向左，求他们到达目的地的最大值。
思路：
因为每个格子只能走一次，那么这两条路不互相影响，那么第二个人从右下角到左上角其实也可以看成从左上角到右下角。
那么可以设状态为f[k][i1][i2]来表示同时从（1，1）走到（i1,j1）和（i2，j2）的时候取到的最大值。
那么有个问题就是不能走到同一个格子，那么我们当枚举到f[k][i1][i2]时，如果（i1，j1）和（i2，j2）是同一个格子就将这个状态设为-INF，这样后续的状态转移就不会用这个状态来转移，但是注意（1,1）和（n，m）这两个格子是都需要走的，那么就特判一下当两个格子相同且不是（1，1）和（n，m）的情况下状态设为-INF,其他的和上个题的思路一样。
#include<bits/stdc++.h>
using namespace std;
const int N=100;
int f[N][N][N];
int a[N][N];
int n,m;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
memset(f,-0x3f,sizeof f);
f[2][1][1]=a[1][1];
for(int k=2;k<=n+m;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<=m&&j2>=1&&j2<=m){
int &x=f[k][i1][i2];
if(i1==i2&&k!=2&&k!=n+m){
x=-0x3f3f3f3f;
continue;
}
int t=a[i1][j1]+a[i2][j2];
x=max(x,f[k-1][i1-1][i2-1]+t);
x=max(x,f[k-1][i1][i2]+t);
x=max(x,f[k-1][i1-1][i2]+t);
x=max(x,f[k-1][i1][i2-1]+t);
}
}
}
}
cout<<f[n+m][n][n]<<endl;
return 0;
}
免费馅饼
原题链接：https://acm.hdu.edu.cn/showproblem.php?pid=1176
题意：
有一个0~10的坐标轴，一个人刚开始在下标为5的位置上，天上要掉n个馅饼，在t秒的时候在位置为x的地方掉一个馅饼，但是这个人每次只能向左或向右走一步，亦或者是待在原地，求他最多能接到多少个馅饼。
思路：
f[i][j]表示在第i秒的时候在位置j的地方接到的馅饼的最大值，那么状态上一秒在j，或者j-1，或者j+1，那么状态转移方程就是：
f[i][j]=max(f[i][j],f[i-1][j]+a[i][j]);
f[i][j]=max(f[i][j],f[i-1][j-1]+a[i][j]);
f[i][j]=max(f[i][j],f[i-1][j+1]+a[i][j]);
判断一下边界情况即可。
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=1e5+10;
int f[N][20];
int a[N][20];
int main(){
while(cin>>n,n){
memset(f,-0x3f,sizeof f);
memset(a,0,sizeof a);
f[0][5]=0;
int mx=0;
for(int i=1;i<=n;i++){
int t,x;
cin>>x>>t;
mx=max(t,mx);
a[t][x]++;
}
for(int i=1;i<=mx;i++){
for(int j=0;j<=10;j++){
f[i][j]=max(f[i][j],f[i-1][j]+a[i][j]);
if(j-1>=0&&j-1<=10)f[i][j]=max(f[i][j],f[i-1][j-1]+a[i][j]);
if(j+1>=0&&j+1<=10)f[i][j]=max(f[i][j],f[i-1][j+1]+a[i][j]);
}
}
int ans=0;
for(int i=0;i<=10;i++) ans=max(ans,f[mx][i]);
cout<<ans<<endl;
}
return 0;
}