记录编号	49374	评测结果	AAAAAAAAAA
题目名称	1253.[IOI 1999] 花店橱窗	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.023 s
提交时间	2012-11-07 18:45:07	内存使用	3.29 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

int val[110][110],f[110][110],rec[110][110];

void printway(int deep,int pos)
{
	if (rec[deep][pos])
	{
		printway(deep-1,rec[deep][pos]);
		cout<<' '<<pos;
	}
	else
		cout<<pos;
}

int main(void)
{
	freopen("hana.in","r",stdin);
	freopen("hana.out","w",stdout);
	int i,j,k,nf,nv,maxnum=0,maxpos;
	cin>>nf>>nv;
	for (i=1;i<=nf;i++)
		for (j=1;j<=nv;j++)
			cin>>val[i][j];
	for (i=1;i<=nf;i++)
		for (j=i;j<=nv;j++)
		{
			f[i][j]=f[i-1][i-1]+val[i][j];
			rec[i][j]=i-1;
			for (k=i;k<j;k++)
			{
				if (f[i][j]<f[i-1][k]+val[i][j])
				{
					f[i][j]=f[i-1][k]+val[i][j];
					rec[i][j]=k;
				}
			}
		}
	for (i=nf;i<=nv;i++)
		if (maxnum<f[nf][i])
		{
			maxnum=f[nf][i];
			maxpos=i;
		}
	cout<<maxnum<<endl;
	printway(nf,maxpos);
	cout<<endl;
	return(0);
}