记录编号	175836	评测结果	AAAAAAAAAA
题目名称	[IOI 1994] 数塔	最终得分	100
用户昵称	啊吧啦吧啦吧	是否通过	通过
代码语言	C++	运行时间	0.010 s
提交时间	2015-08-07 10:29:10	内存使用	0.39 MiB

#include <iostream>
#include <fstream>

using namespace std;

const int MAXN(81);
ifstream fin("shuta.in");
ofstream fout("shuta.out");
#define cin fin
#define cout fout
int n, num[MAXN][MAXN], dp[MAXN][MAXN],r[MAXN][MAXN] = {0};

main()
{
	cin >> n;
	for (int i = 1; i <= n; ++i)
	    for (int j = 1; j <= i; ++j){
	        cin >> num[i][j];
	        dp[i][j] = num[i][j];
	    }

	for (int i = n - 1; i > 0; --i)
	    for (int j = 1; j <= i; ++j)
			if (dp[i + 1][j] >= dp[i + 1][j + 1]){
				dp[i][j] += dp[i + 1][j];
				r[i][j] = j;
			}
			else{
				dp[i][j] += dp[i + 1][j + 1];
				r[i][j] = j + 1;
			}
			
	cout << dp[1][1] << endl << num[1][1];
	int j = 1, i = 1;
	while(r[i][j]){
		cout << ' ' << num[i + 1][r[i][j]];
		j = r[i++][j];
	}
//	for(;;);
}