记录编号	163888	评测结果	WWWWWWWWWW
题目名称	[IOI 1999] 花店橱窗	最终得分	0
用户昵称	0	是否通过	未通过
代码语言	C++	运行时间	0.004 s
提交时间	2015-05-27 08:18:33	内存使用	0.39 MiB

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cctype>
#include <algorithm>
 
using namespace std;
 
const int INF=-0x3fffffff;
 
int F,V;
int a[101][101];
int f[101][101];
int path[101][101];
int pa[101];
 
inline int in()
{
    char c=getchar();
    int x=0;
    while(c<'0'||c>'9')c=getchar();
    for(; c>='0'&&c<='9'; c=getchar())x=x*10+c-'0';
    return x;
}
 
void out(int i,int pos)
{
    if(i==1)
    {
        pa[i]=pos;
        return ;
    }
    out(i-1,path[i][pos]);
    pa[i]=pos;
}
 
int main()
{
	freopen("hana.in","r",stdin);
	freopen("hana.out","w",stdout);
    int i,j,k,l,p;
    F=in();V=in();
    for(i=1;i<=F;++i)
      for(j=1;j<=V;++j)
        a[i][j]=in(),f[i][j]=INF;
    for(i=1;i<=V-F+1;++i)
      f[1][i]=a[1][i],path[1][i]=i;
    for(i=1;i<=F;++i)
    {
      l=V-F+i; 
      for(j=i;j<=l;++j)
        for(k=j+1;k<=l+1;k++)
          if(f[i][j]+a[i+1][k]>f[i+1][k])
            f[i+1][k]=f[i][j]+a[i+1][k],path[i+1][k]=j;//通过j点到达      
    }
    p=F;
    for(i=p;i<=V;++i)
      if(f[F][i]>f[F][p])
        p=i;
    printf("%d\n",f[F][p]);
    out(F,p);
    for(i=1;i<=F;++i)
      printf("%d ",pa[i]);   
}