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

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int f[2010],a[2010],fa[2010],n;
int main()
{
  freopen("cutrod.in","r",stdin);
  freopen("cutrod.out","w",stdout);
  scanf("%d",&n);
  memset(f,128,sizeof(f));
  f[0]=0;
  for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
  for(int i=1;i<=n;i++)
    for(int j=i;j<=n;j++)
      if(f[j-i]>=0)
        if(f[j]<=f[j-i]+a[i])
        {
          f[j]=f[j-i]+a[i];
          fa[j]=j-i;
        }
  cout<<f[n]<<endl;
  int ans[2010],tot=0;
  for(int i=n;i;i=fa[i])
    ans[++tot]=i-fa[i];
  sort(ans+1,ans+1+tot);
  for(int i=tot;i>0;i--)
    cout<<ans[i]<<" ";
  fclose(stdin);fclose(stdout);
  return 0;
}