USACO Section 1.5: Number Triangles
5937 ワード
1 /*
2 ID: leetcod3
3 PROG: numtri
4 LANG: C++
5 */
6 #include <iostream>
7 #include <fstream>
8 #include <string>
9 #include <map>
10 #include <vector>
11 #include <set>
12 #include <algorithm>
13 #include <queue>
14 #include <cmath>
15 #include <list>
16 #include <cstring>
17 #include <cstdlib>
18 #include <limits>
19 #include <stack>
20
21 using namespace std;
22
23 ofstream fout ("numtri.out");
24 ifstream fin ("numtri.in");
25
26 int main()
27 {
28 int R;
29 fin >> R;
30 vector<vector<int> > num;
31 for (int i = 1; i <= R; i++) {
32 vector<int> input(i);
33 for (int j = 0; j < i; j++) fin >> input[j];
34 num.push_back(input);
35 }
36 for (int i = 1; i < R; i++) {
37 for (int j = 0; j < num[i].size(); j++) {
38 if (j == 0) num[i][j] += num[i-1][j];
39 else if (j == num[i].size()-1) num[i][j] += num[i-1][num[i-1].size()-1];
40 else num[i][j] += max(num[i-1][j-1], num[i-1][j]);
41 }
42 }
43 int ans = 0;
44 for (int i = 0; i < R; i++) ans = max(ans, num[R-1][i]);
45 fout << ans << endl;
46 return 0;
47 }