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

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 namespacestd;
11 int a[1010][1010];
12 long long  dp[1010][1010];
13 intmain()
14 {
15     freopen("numtri.in","r",stdin);
16     freopen("numtri.out","w",stdout);
17     intn,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 }