19036: 数字三角形

19036: 数字三角形

时间限制: 1 Sec   内存限制: 128 MB
提交状态

题目描述

上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。

路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右边的那个数。此外，向左下走的次数与向右下走的次数相差不能超过1。

输入

输入的第一行包含一个整数N（1<N≤100），表示三角形的行数。下面的N行给出数字三角形。数字三角形上的数都是0至100之间的整数。

输出

输出一个整数，表示答案。

样例输入 Copy

5

6

0 9

2 4 6

2 3 4 4

6 4 8 7 6

样例输出 Copy

33

这道题和普通的数字三角形不一样。他要求向左下走的次数与向右下走的次数相差不能超过 1。

那其实通过仔细思考发现，最后一行中间这三个，无论通过什么路径都必定满足条件；其他的位置必定不满足条件。（也就是说从顶部到某一定点，左下走的次数和右下走的次数一定是定值）

所以代码如下：

#include<bits/stdc++.h>

using namespace std;

int main(){

int n;

int a[105][105];

scanf("%d",&n);

memset(a,0,sizeof(a));

for(int i=1;i<=n;i++)

for(int j=1;j<=i;j++) scanf("%d",&a[i][j]);

int dp[105][105],left[105][105],right[105][105];

memset(left,0,sizeof(left));

memset(right,0,sizeof(right));

dp[1][1]=a[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]+a[i][j];

left[i][j]=left[i-1][j]+1;

right[i][j]=right[i-1][j];

}

else if(j==i){

dp[i][j]=dp[i-1][i-1]+a[i][j];

left[i][j]=left[i-1][i-1];

right[i][j]=right[i-1][i-1]+1;

}

else{

dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j];

if(dp[i][j]==dp[i-1][j]+a[i][j]){

left[i][j]=left[i-1][j]+1;

right[i][j]=right[i-1][j];

}

else{

left[i][j]=left[i-1][j-1];

right[i][j]=right[i-1][j-1]+1;

}

}

}

int maxx=0;

for(int i=1;i<=n;i++)

if(abs(left[n][i]-right[n][i])<=1)

maxx=max(maxx,dp[n][i]);

cout<<maxx<<endl;

return 0;

}