题目描述

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

const int N = 510;
int dp[N][N],m[N][N];

int n;

int main()
{
cin>>n;

for(int i=1;i<=n;i++)
    for(int j=1;j<=i;j++)
        cin>>m[i][j];

dp[1][1]=m[1][1];

for(int i=2;i<=n;i++)
    for(int j=1;j<=i;j++)
        if(j==1)
            dp[i][j]=dp[i-1][j]+m[i][j];
        else if(j==i)
            dp[i][j]=dp[i-1][j-1]+m[i][j];
        else
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+m[i][j];

int res=-0x3f3f3f3f;

for(int i=1;i<=n;i++)
    res=max(res,dp[n][i]);
cout << res <<endl;

return 0;

}

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla