Sgu104

1046 ワード

花屋のショーウインドーの問題は、言うまでもないでしょう.誰もが知っています.
/*
 *Name:Little shop of flowers
 *LANG:C++
 *Source:sgu104
 */
#include <cstdio>
#include <cstring>
#define INF -0x7FFFFFFF/2
using namespace std;

int a[200][200],ff[200][200];
int f,v,max=INF;

void print(int x,int y){
    if (x>0){
	int i=x;
	while (ff[x][i]!=y) ++i;
	print(x-1,y-a[x][i]);
	printf("%d",i);
	if (x!=f) printf(" ");
	else printf("
"); } } int main(){ scanf("%d %d",&f,&v); for (int i=1;i<=f;++i) for (int j=1;j<=v;++j) scanf("%d",&a[i][j]); for (int i=0;i<=110;++i) for (int j=0;j<=110;++j) ff[i][j]=INF; for (int i=0;i<=v;++i) ff[0][i]=0; for (int i=1;i<=f;++i) for (int j=i;j<=v;++j) for (int k=0;k<j;++k) if (ff[i-1][k]+a[i][j]>ff[i][j]) ff[i][j]=ff[i-1][k]+a[i][j]; for (int i=1;i<=v;++i) if (max<ff[f][i]) max=ff[f][i]; printf("%d
",max); print(f,max); return 0; }