【我为标程写注释】最大值最小化

3.最大值最小化

题目描述：

把一个包含n 个正整数的序列划分为m 个连续的子序列(每个正整数恰

好属于一个序列)。设第i 个序列的各数之和为S(i)，你的任务是让所

有S(i)的最大值尽量小。例如序列1 2 3 2 5 4 划分成3 个序列的最优

方案为1 2 3|2 5 |4，其中S(1)、S(2)、S(3)分别为6、7、4，最大值

为7；如果划分成1 2|3 2|5 4，则最大值为9，不如刚才的好。

n<=10^6，所有数之和不超过10^9。

输入格式：

第一行输入n，m(1<=m<=n<=10^6)。

接下来一行输入n 个正整数，每个数不超过1000。

输出格式：

输出答案。

嗯嗯这道题标程用的是二分搜索……gg说可以用dp……

小声问一句dp是什么……

再问一句二分是什么……

先是二分

 1 /*
 2     写代码人：std（不
 3     批注人：zx 
 4     指导老师：gg 
 5 */
 6 #include<cstdio>
 7 using namespace std;
 8 long a[1000001],alen,gps,big = 0;
 9 long long sum_a = 0;
10 bool Check(long num,long lim) //判断是往左还是往右 
11 {
12     long all = 1,i,sum = 0;
13     for(i=1;i<=alen;i++)
14     {
15         sum += a[i];
16         if(sum > num)
17         {
18             all++;
19             if(all > lim)    return false;    //只有比较小的时候才会出现了 
20             sum = a[i];
21         }
22     }
23     return true;
24 }
25 long long Binary_Divide(long long l,long long r)    //二分本体 
26 {
27     long long i = l,j = r,m;
28     while(i <= j)
29     {
30         m = (i + j) / 2;    //√ 
31         if(Check(m,gps) == true)    j = m - 1;
32         else    i = m + 1;
33     }
34     return i;
35 };
36 int main()
37 {
38     long i;
39     scanf("%ld%ld",&alen,&gps);
40     for(i = 1;i <= alen;i++)
41     {
42         scanf("%ld",&a[i]);
43         if(big < a[i])    big = a[i];    //最大值 
44         sum_a += a[i];    //求和 
45     }
46     printf("%lld",Binary_Divide(big,sum_a));
47     return 0;
48 }

Gg说的dp也在这里写一下

F[I,j] = min(max(f[i-1,j-1],s[i]-s[k]))或s[i](j=1)