数字三角形模型
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);