_Eterna1 @ 2017-08-11 21:34:12
#include <cstdio>
#include <iostream>
using namespace std;
int max(int i,int j);
int main()
{
int i,j,n,ans=0,a[1000][1000];
scanf("%d",&n);
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)scanf("%d",&a[i][j]);
int max=0,tempj;
bool lf;
for(j=1;j<=n;j++)
{
if(a[n-1][j]+a[n][j]>max)
{
max=a[n-1][j]+a[n][j];
lf=true;
tempj=j;
}
if(a[n-1][j-1]+a[n][j]>max)
{
max=a[n-1][j-1]+a[n][j];
lf=false;
tempj=j;
}
}
ans+=a[n][tempj];
printf("%d %d\n",tempj,a[n][tempj]);
j=tempj;
for(i=n-1;i>=2;i--)
{
if(lf==true)ans+=a[i][j];else
{
j--;
ans+=a[i][j];
}
if(a[i-1][j]>a[i-1][j-1])lf=true;
if(a[i-1][j]<a[i-1][j-1])lf=false;
printf("%d %d\n",j,a[i][j]);
}
ans+=a[1][1];
// printf("%d %d %d\n",a[n][tempj],tempj,lf);
printf("%d",ans);
return 0;
}
//7
//3 8
//8 1 0
//2 7 4 4
//4 5 2 6 5by _Eterna1 @ 2017-08-12 11:01:42
我的思路
读入以后，把最后一行中每个数过一遍，把加上它上面左右两个最大的找出来并确定方向
从n-1行开始倒着向上找（方法同上）并累加直到顶端得出答案
by HHCY @ 2017-08-30 11:31:38
#include<cstdio>
#include<algorithm>
using namespace std;
int n,a[1002][1002];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
scanf("%d",&a[i][j]);
for(int i=n;i>=2;i--)
for(int j=1;j<i;j++)
a[i-1][j]+=max(a[i][j],a[i][j+1]);
printf("%d",a[1][1]);
return 0;
}