记录编号	60469	评测结果	AAAAAAAAAAAAAAA
题目名称	钢条切割	最终得分	100
用户昵称	digital-T	是否通过	通过
代码语言	C++	运行时间	0.102 s
提交时间	2013-05-25 14:17:14	内存使用	0.36 MiB

#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
ifstream fi("cutrod.in");
ofstream fo("cutrod.out");
int p[2001],n,f[2001],h[2001];
vector <int> g[2001];
bool op(int x,int y)
{
	if(x>y)return 1;
	return 0;
}
int main()
{
	fi>>n;
	int i,j,k;
	for(i=1;i<=n;i++)
	{
		fi>>p[i];//p[i]表示i长度的价值
		f[i]=p[i];
		g[i].push_back(i);
		h[i]=1;
	}
	for(i=2;i<=n;i++)
	{
		for(j=1;j<=i-1;j++)
		if((f[i]<f[j]+f[i-j])||(f[i]==f[j]+f[i-j]&&h[i]>h[j]+h[i-j]))//切吧
		{
			f[i]=f[j]+f[i-j];
			h[i]=g[j].size()+g[i-j].size();
			g[i].clear();
			for(k=0;k<g[j].size();k++)
				g[i].push_back(g[j][k]);
			for(k=0;k<g[i-j].size();k++)
				g[i].push_back(g[i-j][k]);
		}
	}
	fo<<f[n]<<endl;
	sort(g[n].begin(),g[n].end(),op);
	for(i=0;i<g[n].size();i++)fo<<g[n][i]<<' ';
	return 0;
}