题解 P1216 【[USACO1.5]数字三角形 Number Triangles】

zengqinyi · 2017-08-27 21:53:16 · 题解

楼下几位大佬貌似都用的是从下往上推的，

这里讲一下从上往下推的做法。

步骤：

（1）读入；

（2）a[i][j]代表从上往下到达i行j列这个点所能达到的和的最大值，

从上往下到达（i，j）这个点所能达到的和的最大值，即为其上方和左上方两个数中大的那个加上它本身的值。

a[i][j]+=max(a[i-1][j-1],a[i-1][j]);//本题最重要的步骤 

（3）最后在最底下一层中找出最大的值输出就可以了。

以下为代码：

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
using namespace std;
#define rint register int
inline void read(int &x)//读入优化 
{
    x=0;int w=1;char ch=getchar();
    while(!isdigit(ch)&&ch!='-')ch=getchar();
    if(ch=='-')w=-1,ch=getchar();
    while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^'0'),ch=getchar();
    x=x*w;
}
const int maxn=1000+10;
int n,a[maxn][maxn],ans; 
int main()
{
    read(n);
    for(rint i=1;i<=n;i++)
    {
        for(rint j=1;j<=i;j++)
        {
            read(a[i][j]);
            a[i][j]+=max(a[i-1][j-1],a[i-1][j]);//本题最重要的步骤 
            //a[i][j]代表从上往下到达i行j列这个点所能达到的和的最大值 
            ans=max(ans,a[i][j]);//在所有答案中找最大的（与在最底下一层找最大值是一样的）
        }
    }//边读入边计算，随手优化一下常数（其实只是懒得打for循环） 
    cout<<ans<<endl;
    return 0; 
}