记录编号	557661	评测结果	AAAAAAAAAA
题目名称	[IOI 1994] 数塔	最终得分	100
用户昵称	卢本伟	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2020-11-20 17:50:34	内存使用	0.00 MiB

#include<iostream>
#include<cstdio>
using namespace std;
int dfs(int,int); 
int n,f[1001][1001],a[1001][1001],b[1001][1001];
int main()
{
	freopen("shuta.in","r",stdin);
	freopen("shuta.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=i;j++)
	{
	cin>>a[i][j];
	if(i==n) f[n][j]=a[i][j];
    }
    for(int i=n-1;i>=1;i--)
    for(int j=1;j<=i;j++)
	if(f[i+1][j]>=f[i+1][j+1])
    {
	f[i][j]=a[i][j]+f[i+1][j];
	b[i][j]=j;
	}
    else 
	{
	f[i][j]=a[i][j]+f[i+1][j+1];
	b[i][j]=j+1;
	}
    cout<<f[1][1]<<endl;
    dfs(1,1);
}
int dfs(int x,int y)
{
	if(x==n+1) return 0;
	cout<<a[x][y]<<" ";
	dfs(x+1,b[x][y]);
}