poj1157花店橱窗(以花作为阶段）.cpp

poj1157

#include<iostream>
using namespace std;
const int N=101;
int main()
{
	int value[N][N],array[N][N],pos[N][N];
	int f,v;
	int i,j,k,l;
	int max_result=-INT_MAX;
	cin>>f>>v;
	for(i=1;i<=f;i++)
		for(j=1;j<=v;j++)
		{
			cin>>value[i][j];
			array[i][j]=-INT_MAX;
		}
		array[1][1]=value[1][1];
		pos[1][1]=1;
		for(i=2;i<=v;i++)
		{
			if(array[1][i-1]<value[1][i])
			{
				array[1][i]=value[1][i];
				pos[1][i]=i;
			}
			else
			{
				array[1][i]=array[1][i-1];
				pos[1][i]=pos[1][i-1];
			}
		}
		for(i=2;i<=f;i++)
			for(j=i;j<=v;j++)
			{
				for(l=i-1;l<j;l++)
					for(k=pos[i-1][l]+1;k<=j;k++)
					{
						if(array[i][j]<array[i-1][l]+value[i][k])
						{
							array[i][j]=array[i-1][l]+value[i][k];
							pos[i][j]=k;
						}
					}
			}
			for(i=f;i<=v;i++)
				if(max_result<array[f][i])
					max_result=array[f][i];
			cout<<max_result<<endl;
			return 0;
}