usaco1.51Number Triangles（数字三角形）

最基础的数字三角形
View Code
 1 #include <iostream>
 2 #include<cstdio>
 3 /*
 4 ID: your_id_here
 5 PROG: numtri
 6 LANG: C++
 7 */
 8 #include<cstring>
 9 #include<algorithm>
10 using namespace std;
11 int a[1010][1010];
12 long long  dp[1010][1010];
13 int main()
14 {
15     freopen("numtri.in","r",stdin);
16     freopen("numtri.out","w",stdout);
17     int n,i,j;
18     cin>>n;
19     for(i = 1; i <= n; i++)
20     for(j = 1; j <= i ; j++)
21     {
22         cin>>a[i][j];
23         dp[i][j] = a[i][j];
24     }
25     for(i = n-1; i >= 1 ; i--)
26     for(j = 1 ; j <= i ; j++)
27     {
28         dp[i][j] = max(dp[i+1][j]+a[i][j],dp[i+1][j+1]+a[i][j]);
29     }
30     cout<<dp[1][1]<<endl;
31     fclose(stdin);
32     fclose(stdout);
33     return 0;
34 }