数字三角形模型

1015. 摘花生

https://www.acwing.com/problem/content/1017/
方程定义成从下往上走 最大值写法

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<unordered_map>
using namespace std;
typedef long long LL;
int T,R,C;
int a[105][105];
int f[105][105];
int main(){
    cin>>T;
    while(T--){
        cin>>R>>C;
        memset(a,0,sizeof(a));
        memset(f,0,sizeof(f));
        for(int i=1;i<=R;i++){
            for(int j=1;j<=C;j++){
                scanf("%d",&a[i][j]);
            }
        }
        for(int i=R;i>=1;i--){
            for(int j=C;j>=1;j--){
                f[i][j]=max(f[i+1][j],f[i][j+1])+a[i][j];
            }
        }
        cout<<f[1][1]<<endl;
    }
  return 0;
}
//  freopen("testdata.in", "r", stdin);

方程按题意定义从上往下走写法 数组从1开始就可以避免越界问题

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<unordered_map>
using namespace std;
typedef long long LL;
int T,R,C;
int a[105][105];
int f[105][105];
int main(){
    cin>>T;
    while(T--){
        cin>>R>>C;
        memset(a,0,sizeof(a));
        memset(f,0,sizeof(f));
        for(int i=1;i<=R;i++){
            for(int j=1;j<=C;j++){
                scanf("%d",&a[i][j]);
            }
        }
        for(int i=1;i<=R;i++){
            for(int j=1;j<=C;j++){
                f[i][j]=max(f[i-1][j],f[i][j-1])+a[i][j];
            }
        }
        cout<<f[R][C]<<endl;
    }
  return 0;
}
//  freopen("testdata.in", "r", stdin);

1018. 最低通行费

https://www.acwing.com/problem/content/1020/
不可能出现往左走和往上走的情况 所以实际上和上面那题一样

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<unordered_map>
using namespace std;
typedef long long LL;
int N;
int a[105][105];
int f[105][105];
int main(){
    cin>>N;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            cin>>a[i][j];
        }
    }
    memset(f,0x3f,sizeof(f));
    f[1][1]=0;
    f[1][0]=0;//初始化边界
    f[0][1]=0;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            f[i][j]=min(f[i][j-1],f[i-1][j])+a[i][j];
        }
    }
    cout<<f[N][N]<<endl;
  return 0;
}
//  freopen("testdata.in", "r", stdin);

最长上升子序列模型

1017. 怪盗基德的滑翔翼

https://www.acwing.com/problem/content/1019/
求一遍最长上升和最长下降

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<unordered_map>
using namespace std;
typedef long long LL;
int T;
int a[105];
int f1[105];
int f2[105];
int main(){
    cin>>T;
    while(T--){
        int n;
        cin>>n;
        memset(a,0,sizeof(a));
        memset(f1,0,sizeof(f1));
        memset(f2,0,sizeof(f2));
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        for(int i=1;i<=n;i++){
            f1[i]=1;
            for(int j=1;j<i;j++){
                if(a[j]>=a[i]){
                    f1[i]=max(f1[i],f1[j]+1);
                }
            }
        }
        for(int i=1;i<=n;i++){
            f2[i]=1;
            for(int j=1;j<i;j++){
                if(a[j]<=a[i]){
                    f2[i]=max(f2[i],f2[j]+1);
                }
            }
        }
        int ans=0;
        for(int i=1;i<=n;i++){
            ans=max(ans,max(f1[i],f2[i]));
        }
        cout<<ans<<endl;
    }
  return 0;
}
//  freopen("testdata.in", "r", stdin);