AcWing 898. 数字三角形
原题链接
简单
作者:
Value
,
2020-05-29 23:40:36
,
所有人可见
,
阅读 733
理解写法
#include <iostream>
#include <cstring>
#define inf 0x3f3f3f
using namespace std;
const int N = 510;
int a[N][N], f[N][N];
int main(){
int n; cin >> n;
for(int i = 1; i <= n; i ++ ){
for(int j = 1; j <= i; j ++ ) cin >> a[i][j];
}
memset(f, -inf, sizeof f);
f[0][0] = 0;
for(int i = 1; i <= n; i ++ ){
for(int j = 1; j <= i; j ++ ){
// [i - 1][j]为左方元素,上一行最大列 = 上一行行号,即:i - 1, [i - 1 <= j] ==> [i][j]上面有元素
if(i - 1 >= j) f[i][j] = max(f[i][j], f[i - 1][j]);
// [i - 1][j - 1]为右上方元素, [j - 1 > 0] ==> [i][j]左上方有元素
if(j - 1 >= 0) f[i][j] = max(f[i][j], f[i - 1][j - 1]);
f[i][j] += a[i][j];
}
}
int res = 0;
for(int i = 1; i <= n; i ++ ) res = max(f[n][i], res);
cout << res << endl;
return 0;
}
其实可以不用if判断
#include <iostream>
#include <cstring>
using namespace std;
const int N = 510;
int a[N][N], f[N][N];
int main(){
int n;
cin >> n;
for(int i = 1; i <= n; i ++ ){
for(int j = 1; j <= i; j ++ ){
cin >> a[i][j];
}
}
memset(f, -0x3f3f3f, sizeof f);
f[0][0] = 0; // 定义一个入口
for(int i = 1; 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 res = -0x3f3f3f3f;
for(int i = 1; i <= n; i ++ ) res = max(res, f[n][i]);
cout << res << endl;
return 0;
}