记录编号	60467	评测结果	AAAAAAAAAAAAAAA
题目名称	钢条切割	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C++	运行时间	0.053 s
提交时间	2013-05-25 13:34:30	内存使用	0.34 MiB

#include <fstream>
#include <algorithm>
using namespace std;
ifstream fi("cutrod.in");
ofstream fo("cutrod.out");
int n,a[2001],ans,f[2001],s[2001],p[2001];
void init()
{
	int i;
	fi>>n;
	for (i=1;i<=n;i++) fi>>a[i];s[1]=1;
	for (i=1;i<=n;i++) f[i]=-1;f[1]=a[1];
}
int dp(int x,int y)
{
	int i,temp,ans=-999999999;
	if (x>y) return 0;
	if (x==y) return a[1];
	if (f[y-x+1]!=-1) return f[y-x+1];
	if (a[y-x+1]>ans) {ans=a[y-x+1];s[y-x+1]=y-x+1;}
	for (i=x;i<y;i++)
	{
		if (f[i-x+1]==-1) temp=dp(x,i)+a[y-i];else temp=f[i-x+1]+a[y-i];
		if (temp>ans) {ans=temp;s[y-x+1]=y-i;}
	}
	f[y-x+1]=ans;
	return ans;
}
bool cmp(int x,int y)
{
	if (x>y) return true;else return false;
}
int main()
{
	int m=0,i;
	init();
	fo<<dp(1,n)<<endl;
	while (n>0)
	{
		p[++m]=s[n];n-=s[n];
	}
	sort(p+1,p+m+1,cmp);
	for (i=1;i<=m;i++) fo<<p[i]<<' ';
	return 0;
}