学步园

把一个有n的非负元素的数组划分为k部分（各个部分的元素在原数组中必须是连续的，就是{i, i+1,...,j}），使得k个部分各个部分元素的和中的最大值最小，返回这个值。
比如把{10, 20， 30, 40, 50, 60, 70, 80, 90}划分为3部分，那么这种划分是一种方案：
第一部分：10 20 30 40 50
第二部分：60 70
第三部分：80 90

http://boj.me/onlinejudge/showproblem.php?problem_id=1461

DP方法：O(n*n*n)

#include<iostream><br /> using namespace std;<br /> const int INF = 1000000000;<br /> const int SIZE = 210;<br /> int v[SIZE], dp[SIZE][SIZE];<br /> int main()<br /> {<br /> int i, j, k, n, m, temp, s;<br /> while(scanf("%d%d", &n, &m) && (n || m))<br /> {<br /> v[0] = 0;<br /> for(i = 1; i <= n; i ++)<br /> {<br /> scanf("%d", &v[i]);<br /> v[i] += v[i - 1];<br /> }<br /> for(i = 1; i <= n; i ++)<br /> dp[1][i] = v[i];<br /> for(k = 2; k <= m; k ++)<br /> {<br /> s = k;<br /> for(j = k; j <= n; j ++)<br /> {<br /> temp = INF;<br /> for(i = s; i <= j; i ++)<br /> {<br /> int tmp = max(dp[k - 1][i - 1], v[j] - v[i - 1]);<br /> if(temp > tmp) { temp = tmp;s = i;}<br /> }<br /> dp[k][j] = temp;<br /> }<br /> }<br /> printf("%d/n", dp[m][n]);<br /> }<br /> }<br />

还有一种是 二分方法，复杂度是 nlog(sum),sum为n个元素的总和

 #include <iostream><br /> using namespace std;<br /> int data[205];<br /> int N,M;<br /> int greedPartion(long long mid)<br /> {//按最大不超过mid值，对data数组进行 贪心划分,返回划分数<br /> int cnt = 0;<br /> int i = 0;<br /> while(i<N)<br /> {<br /> long long part = 0;<br /> while(i<N && part+data[i] <= mid)<br /> {<br /> part += data[i];<br /> i++;<br /> }<br /> cnt++;<br /> }<br /> return cnt;<br /> }<br /> long long fun(long long s,long long e)<br /> {<br /> while(s <= e)<br /> {<br /> long long mid = s+(e-s)/2;<br /> //对原数组进行划分，使每一段 之和 不超过mid值<br /> int cnt = greedPartion(mid);<br /> if(cnt <= M)//划分次数 <= 目标次数，说明e 太大了<br /> {<br /> e = mid -1;<br /> }<br /> else<br /> {<br /> s = mid +1;<br /> }<br /> }<br /> return s;<br /> }<br /> int main()<br /> {<br /> while(cin>>N>>M,N||M)<br /> {<br /> long long sum = 0;<br /> long long maxv = 0;<br /> for(int i=0;i<N;i++)<br /> {<br /> scanf("%d",&data[i]);<br /> sum += data[i];<br /> if(data[i] > maxv) maxv = data[i];<br /> }</p> <p> cout<<fun(maxv,sum)<<endl;<br /> }<br /> return 0;<br /> }