这个题就是一个动归，和乘积最大一样，处理前缀和，枚举当前位置和划分层数，找最大的时间，取最小值1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;int a[999999],f[3999][3999],m,n,s[999999];
int print(int x,int y){
if(y==0) return 0;
if(y==1){
printf("1 %d\n",x);
return 0;
}
int t=x,w=a[x];
while(w+a[t-1]<=f[m][n]){
w+=a[t-1];
t--;
}
print(t-1,y-1);
printf("%d %d\n",t,x);
}
int main()
{
scanf("%d%d",&n,&m);
memset(f,127,sizeof(f));
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
s[i]=s[i-1]+a[i];
f[1][i]=s[i];
}
for(int i=2;i<=m;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=j-1;k++)
{
if (max(f[i-1][k],s[j]-s[k])<f[i][j])
f[i][j]=max(f[i-1][k],s[j]-s[k]);
}
//printf("%d",f[m][n]);
print(n,m);
}
也可以二分答案
对时间进行二分答案，如果人数少了，时间就剪短，多了就增加1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49#include<cstdio>
using namespace std;
int m,k;int a[99999],s[99999]; int l,r;
int print(int x,int y){
if(y==0) return 0;
if(y==1){
printf("1 %d\n",x);
return 0;
}
int t=x,w=a[x];
while(w+a[t-1]<=l-1){
w+=a[t-1];
t--;
}
print(t-1,y-1);
printf("%d %d\n",t,x);
}
int check(int x){
int t=a[1];int ans=0;int j=0;
for(int i=2;i<=m;i++)
{
if(t+a[i]>=x)
ans++,t=a[i];
else t+=a[i];
}
return ans;
}
int main()
{
scanf("%d%d",&m,&k);
for(int i=1;i<=m;i++)
{
scanf("%d",&a[i]);
s[i]=s[i-1]+a[i];
}
l=1,r=s[m];
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)>=k)
l=mid+1;
else r=mid-1;
}
//printf("%d",r);
//printf("%d\n",check(16));
print(m,k);
return 0;
}