记录编号	69528	评测结果	AAAAAAAAAAAAAAA
题目名称	钢条切割	最终得分	100
用户昵称	raywzy	是否通过	通过
代码语言	C++	运行时间	0.017 s
提交时间	2013-09-17 19:28:08	内存使用	0.33 MiB

#include<fstream>
using namespace std;
ifstream fin("cutrod.in");
ofstream fout("cutrod.out");
int n;
int a[2001],path[2001],ans[2001];
int flag=0;
int main()
{
	fin>>n;
	int i,j;
	for(i=1;i<=n;i++)
		fin>>a[i];
	for(i=1;i<=n;i++)
	{
		flag=0;
		for(j=1;j<=i;j++)
		{
			if(flag<=a[j]+ans[i-j])
			{
				flag=a[j]+ans[i-j];
				if(j>path[i])
					path[i]=j;
			}
		}
		ans[i]=flag;
	}
	fout<<ans[n]<<endl;
	while(n>0)
	{
		fout<<path[n]<<' ';
		n=n-path[n];
	}
	fout<<endl;
	return 0;
}