Description
给出一个长为
n
n
的整数数列
aa，要求求出最小的
m
m
，使得存在一种将数列分成恰好
KK 份的方案（每份是数列上连续的一段，且不得为空），每份的数字之和不大于
m
m
。
对于
100%100% 的数据满足：
K≤n≤15000,−10000≤a[i]≤10000
K
≤
n
≤
15000
,
−
10000
≤
a
[
i
]
≤
10000
。
Solution
没有负数就是水题。首先想到二分答案
mid
m
i
d
，考虑如何快速判断。设
bool
b
o
o
l
数组
f[i][j]
f
[
i
]
[
j
]
表示分割到序列第
i
i
个位置、分成
jj 个部分、满足每个部分和
≤mid
≤
m
i
d
是否可能，序列前缀和为
s[i]
s
[
i
]
, 则转移为：
f[i][j]|=f[k][j−1](0≤k<i,s[i]−s[k]≤mid)，初始时f[0][0]=true
f
[
i
]
[
j
]
|
=
f
[
k
]
[
j
−
1
]
(
0
≤
k
<
i
,
s
[
i
]
−
s
[
k
]
≤
m
i
d
)
，
初
始
时
f
[
0
]
[
0
]
=
t
r
u
e
设
g[i]={f[i][0],f[i][1],...,f[i][K]}
g
[
i
]
=
{
f
[
i
]
[
0
]
,
f
[
i
]
[
1
]
,
.
.
.
,
f
[
i
]
[
K
]
}
，定义：
g[i]+g[j]={f[i][0] | f[j][0],f[i][1] | f[j][1],...,f[i][K] | f[j][K]}
g
[
i
]
+
g
[
j
]
=
{
f
[
i
]
[
0
]
|
f
[
j
]
[
0
]
,
f
[
i
]
[
1
]
|
f
[
j
]
[
1
]
,
.
.
.
,
f
[
i
]
[
K
]
|
f
[
j
]
[
K
]
}
g[i]<<1={0,f[i][0],f[i][1],...,f[i][K−1]}
g
[
i
]
<<
1
=
{
0
,
f
[
i
]
[
0
]
,
f
[
i
]
[
1
]
,
.
.
.
,
f
[
i
]
[
K
−
1
]
}
转移就变为
g[i]=(∑j=1i−1g[j],s[j]≥s[i]−mid)<<1
g
[
i
]
=
(
∑
j
=
1
i
−
1
g
[
j
]
,
s
[
j
]
≥
s
[
i
]
−
m
i
d
)
<<
1
。把
s[i]
s
[
i
]
按从大到小排序，可知此时合法的
j
j
是一个前缀。
因此把
s[i]s[i] 离散化，作为树状数组的下标维护前缀和来转移。此时
DP
D
P
复杂度
O(nKlogn)
O
(
n
K
log
n
)
，仍然不能通过。进一步地，我们会发现：
g[i]
g
[
i
]
中为
true
t
r
u
e
的部分一定是一段连续的区间，只需要用区间的左右边界来表示。容易证明，一开始
g[0]={1,0,...,0}
g
[
0
]
=
{
1
,
0
,
.
.
.
,
0
}
满足条件，之后的转移只涉及上述两种运算，因此也满足条件。此时就可设
g[i]={l[i],r[i]}
g
[
i
]
=
{
l
[
i
]
,
r
[
i
]
}
，初始时
g[0]={0,0}
g
[
0
]
=
{
0
,
0
}
，则：
g[i]+g[j]={min{l[i], l[j]}, max{r[i], r[j]}}
g
[
i
]
+
g
[
j
]
=
{
min
{
l
[
i
]
,
l
[
j
]
}
,
max
{
r
[
i
]
,
r
[
j
]
}
}
g[i]<<1={l[i]+1, min{r[i]+1, K}}
g
[
i
]
<<
1
=
{
l
[
i
]
+
1
,
min
{
r
[
i
]
+
1
,
K
}
}
因此计算
g[i]
g
[
i
]
的部分就被优化掉了，
DP
D
P
的时间复杂度
O(nlogn)
O
(
n
log
n
)
。
Code
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cctype>
using namespace std;
namespace inout
{
const int S =
1 <<
20;
char frd[S], *ihed = frd + S;
const char *ital = ihed;
inline char inChar()
{
if (ihed == ital)
fread(frd,
1, S, stdin), ihed = frd;
return *ihed++;
}
inline int get()
{
char ch;
int res =
0;
bool flag =
false;
while (!
isdigit(ch = inChar()) && ch !=
'-');
(ch ==
'-' ? flag =
true : res = ch ^
48);
while (
isdigit(ch = inChar()))
res = res *
10 + ch -
48;
return flag ? -res : res;
}
};
using namespace inout;
const int M =
15005;
const int Maxn =
0x3f3f3f3f;
int n, K, m, l = Maxn, r = -Maxn, Ans;
int f[M], g[M], sum[M], to[M], b[M];
inline int Max(
int x,
int y) {
return x > y ? x : y;}
inline int Min(
int x,
int y) {
return x < y ? x : y;}
inline void CkMin(
int &x,
int y) {
if (x > y) x = y;}
inline void CkMax(
int &x,
int y) {
if (x < y) x = y;}
struct line
{
int l, r;
line() {}
line(
int L,
int R):
l(L), r(R) {}
inline void operator += (
const line &x)
{
CkMin(l, x.l); CkMax(r, x.r);
}
}c[M], h[M];
const line Inf = line(Maxn, -Maxn);
inline line Right(
const line &x)
{
if (x.l == K)
return Inf;
return line(x.l +
1, Min(x.r +
1, K));
}
inline void Modify(
int x,
const line &y)
{
for (; x <= n; x += x & -x)
c[x] += y;
}
inline line Query(
int x)
{
line res = Inf;
for (; x; x -= x & -x)
res += c[x];
return res;
}
inline bool check(
int mid)
{
for (
int i =
1; i <= n; ++i) c[i] = Inf;
Modify(to[
0], h[
0] = line(
0,
0));
for (
int i =
1; i < n; ++i)
{
int k = upper_bound(b +
1, b + m +
1, mid - sum[i]) - b -
1;
h[i] = Right(Query(k)); Modify(to[i], h[i]);
}
return h[n -
1].r == K;
}
int main()
{
n = get(); K = get();
for (
int i =
1; i <= n; ++i)
{
f[i] = g[i] = sum[i] = get();
sum[i] += sum[i -
1]; b[i] = -sum[i];
if (f[i -
1] >
0) f[i] += f[i -
1];
if (g[i -
1] <
0) g[i] += g[i -
1];
CkMin(l, g[i]); CkMax(r, f[i]);
}
sort(b +
1, b + n +
2);
m = unique(b +
1, b + n +
2) - b -
1;
for (
int i =
0; i <= n; ++i)
to[i] = lower_bound(b +
1, b + m +
1, -sum[i]) - b;
++n;
while (l <= r)
{
int mid = (l + r) /
2;
if (check(mid)) Ans = mid, r = mid -
1;
else l = mid +
1;
}
printf(
"%d\n", Ans);
return 0;
}
