boj 437

Description
校内赛马上开始了，选手们比赛时，需要打印代码，但是912的打印机被wangkun弄坏了，无法进行打印。wangkun的钱都上交给wmz了，他只有想办法让912的小盆友们手抄代码，然后送给选手们。这里共有n份代码 ，编号1,2,…,n。每份代码有pi页。全部分给m个小盆友。每人分到顺序连续的若干份，每份代码只分给一人。 为了和谐，wangkun需要你，求一种方案，使每人分到的页数总和的最大值为最小. 

Input
每行输入两个n,m （1<=n<=200） 接下来有n个数，是每份代码的页数。 m < n 当 n = 0 并且 m=0时结束。 

Output
输出一行，为每人分到的页数总和的最大值为最小的数. 

Sample Input

9 3
100 200 300 400 500 600 700 800 900
0 0 

Sample Output

1700 

Hint
n=9,m=3
100 200 300 400 500 / 600 700 / 800 900 

Source
wangkun

思路：

最佳解法应该是二分+枚举，但是不会，用dp水过

dp[i][j]表示将1~i个数分成j份，dp[i][j]由dp[k][j-1]构造（k∈[i-1,j-1]）

代码：

#include<iostream>
using namespace std;
int dp[205][205],arr[205];
int main()
{
	int n,m,maxnum,sum = 0;
	while(scanf("%d %d",&n,&m))
	{
		if(n==0&&m==0)break;
		maxnum = 0;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&arr[i]);
			maxnum+=arr[i];
			dp[i][1] = maxnum;
		}
		for(int i=1;i<=n;i++)
		{
			int bound = min(i,m);
			for(int j=2;j<=bound;j++)
			{
				sum = 0;
				dp[i][j] = maxnum;
				for(int k = i-1;k>=j-1;k--)
				{
					sum+=arr[k+1];
					dp[i][j] = min(max(sum,dp[k][j-1]),dp[i][j]);
				}
			}
		}
		printf("%d\n",dp[n][m]);
	}
}