记录编号	163891	评测结果	AAAAAAAAAA
题目名称	[IOI 1999] 花店橱窗	最终得分	100
用户昵称	zys	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2015-05-27 08:27:13	内存使用	0.41 MiB

#include<cstdio>
using namespace std;
const int INF=50000000;
int F,v,a[101][101],f[101][101],d[101][101],ans,x,b[101];//第i种花放在第j个瓶子时的最大值
void DP()
{
	for(int i=1;i<=F;i++)
	    for(int j=1;j<=v;j++)
	        f[i][j]=-INF;
	for(int i=1;i<=v;i++)
	    f[1][i]=a[1][i];
	int gs=v-F;
	for(int i=2;i<=F;i++)
	    for(int j=i;j<=gs+i;j++)
	        for(int k=i-1;k<j;k++)
				if(f[i][j]<f[i-1][k]+a[i][j])
				{
					f[i][j]=f[i-1][k]+a[i][j];
					d[i][j]=k;
				}
	for(int i=F;i<=v;i++)
	    if(f[F][i]>ans)
	    {
		    ans=f[F][i];
		    x=i;
	    }
	printf("%d\n",ans);
	int k=F;
	b[F]=x;
	for(int i=d[F][x];i>0;i=d[k][i])
		b[--k]=i;
	for(int i=1;i<=F-1;i++)
		printf("%d ",b[i]);
	printf("%d",b[F]);
}
int main()
{
    freopen("hana.in","r",stdin);
	freopen("hana.out","w",stdout);
	scanf("%d%d",&F,&v);
	for(int i=1;i<=F;i++)
	    for(int j=1;j<=v;j++)
	        scanf("%d",&a[i][j]);
	 DP();
}