Volume 1 / 0181

Problem 0181 : Persistence

パソコン甲子園2008予選　問題09 こだわり

#include <iostream>
#include <vector>
#include <limits.h>

using namespace std;


int m, n;
vector<int> bw;
vector< vector<int> > bsw;

int calc()
{
	int new_val;
	int i, j, k;

	for( i=1; i<=n; i++ )
		bsw[1][i] = bw[i];

	for( i=1; i<=m; i++ )
		bsw[i][1] = bw[1];


	for( i=2; i<=n; i++ ){
		for( j=2; j<=m; j++ ){
			bsw[j][i] = INT_MAX;
			for( k=1; k<=i-1; k++ ){
				new_val = ( bsw[j-1][k] > bw[i]-bw[k] ) ? bsw[j-1][k] : bw[i]-bw[k];
				if( bsw[j][i] > new_val )
					bsw[j][i] = new_val;
			}
		}
	}

	return bsw[m][n];
}

int main(void)
{
	int i;

	while( cin >> m >> n, m!=0, n!=0 ){
		bsw.clear(); bw.clear();

		bsw.resize(m+1);
		for( i=0; i<=m; i++ )
			bsw[i].resize(n+1);

		bw.resize(n+1); bw[0] = 0;
		for( i=1; i<=n; i++ ){
			cin >> bw[i];
			bw[i] += bw[i-1];
		}

		cout << calc() << endl;	
	}

	return 0;
}