南郵OJ 1230最小m段と問題

最小mセグメントと問題
時間制限(通常/Java):
1000 MS/3000 MS運転メモリ制限:65536 KByte
総提出:114試験合格:48
試合の説明
n個の整数からなるシーケンスが与えられ、シーケンスはmセグメントに分割され、各サブシーケンスの数は元のシーケンスで連続的に配列されることが要求される.どのように分割してこのmネタのシーケンスの和の最大値を最小にすることができますか?
n個の整数からなるシーケンスを与え,そのシーケンスの最適mセグメント分割をプログラミングして計算し,mネタシーケンスの和の最大値を最小にする.
入力
入力された1行目には正の整数nとmが2つあります.正の整数nはシーケンスの長さである.正の整数mは分割された断数である.次の行にはn個の整数があります.
しゅつりょく
出力される1行目の数は、算出されたmネタシーケンスの和の最大値の最小値である.
サンプル入力
1 1 10
サンプル出力
10
ヒント
undefined
テーマソース
アルゴリズム設計と実験問題解

//sum[i][j]:  i    j    
//dp[i][j]: i    j ， j                   

#include<stdio.h>
#include<limits.h>
#define N 101

int a[N];
int sum[N][N];
int dp[N][N];

int main(){
	int n,m,i,j,k,min,max;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++){
		scanf("%d",a+i);
		sum[i][i] = a[i];
	}
	for(i=1; i<=n; i++){
		for(j=i+1; j<=n; j++){
			sum[i][j] = sum[i][j-1]+a[j];
		}
	}
	for(i=1; i<=n; i++){
		dp[i][1] = sum[1][i];
	}
	for(i=2; i<=n; i++){
		for(j=2; j<=m && j<=i; j++){
			min = INT_MAX;
			for(k=j; k<i; k++){
				if(dp[k][j-1] > sum[k+1][i]){
					max = dp[k][j-1];
				}else{
					max = sum[k+1][i]; 
				}
				if(min>max){
					min = max;
				}
			}
			dp[i][j] = min;
		}
	}
	printf("%d
",dp[n][m]);
}