AcWing 898. 数字三角形
原题链接
简单
作者:
初夏风雪
,
2024-03-30 18:29:39
,
所有人可见
,
阅读 6
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <climits>
using namespace std;
const int N=510;
int w[N][N];
int f[N][N];
int main ()
{
int n;
cin>>n;
for (int i=1;i<=n;i++)
{
for (int j=1;j<=i;j++)
{
cin>>w[i][j];
}
}
// for(int i=1;i<=n;i++){
// for(int j=0;j<=i+1;j++){ //因为有负数,所以应该将两边也设为-INF
// f[i][j]=-2e9;
// }
// }
for (int i=0;i<=n;i++)
{
for (int j=0;j<=n;j++)
{
f[i][j]=-2e9;
}
}
f[0][1]=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])+w[i][j];
}
}
int res=-2e9;
for (int k=1;k<=n;k++) res=max(res,f[n][k]);
cout<<res<<endl;
return 0;
}