Complete Partition Of Array
Complete Partition Of Array
1.分成sum相等的k份
若 k = 2 k=2 k=2，显然预处理 s = ∑ i = 1 n a i s=\sum_{i=1}^na_i s=∑i=1nai，然后扫一遍枚举分界点即可。
若 k = 3 k=3 k=3，可以预处理后缀 b i = ∑ j = i n ( [ s u f j = a v g ] ) , a v g = s 3 b_i=\sum\limits_{j=i}^n([suf_j=avg]),avg=\dfrac{s}{3} bi=j=i∑n([sufj=avg]),avg=3s。
然后枚举第一个分界点 i i i，求和即可。
当然也可以使用双指针思路类似。
当 k > 3 k>3 k>3，但不是很大时，可以考虑 d p dp dp。
d p ( i , j ) = d p ( i , j ) + d p ( k , j − 1 ) × [ s u m ( k + 1 , i ) = s u m ( 1 , i ) j ] , k < i dp(i,j)=dp(i,j)+dp(k,j-1)\times [sum(k+1,i)=\dfrac{sum(1,i)}{j}],k<i dp(i,j)=dp(i,j)+dp(k,j−1)×[sum(k+1,i)=jsum(1,i)],k<i
区间和可以预处理前缀和、差分计算。
时间复杂度： O ( n k ) O(nk) O(nk)
1.1 Bouns
当 1 ≤ k ≤ n ≤ 1 0 5 1\le k \le n\le 10^5 1≤k≤n≤105 是否可解呢？
2.分成k份的最大值最小
同理可以dp。
const int MAX_COUNT = 100;
int state[MAX_COUNT][MAX_COUNT];
int a[MAX_COUNT];
int MinSum(int n,int m)
{
int i = 0, j = 0, k = 0, temp = 0, MaxInt;
for (i = 1;i <=n;++i)
{
state[i][1] = state[i-1][1] + a[i];
}
for (j = 2;j <=m;++j)
{
for (i = j; i <= n;++i)
{
temp = 10000000;
for (k = j;k<i;++k)
{
MaxInt = max(state[i][1]-state[k][1],state[k][j-1]);
if (temp > MaxInt)
{
temp = MaxInt;
}
}
state[i][j] = temp;
}
}
return state[n][m];
}
也可以二分贪心，直接二分答案，然后贪心分组。
可以看一下这一题：【uva 714】Copying Books
传送门
最小值最大也可以dp 和 二分贪心。
见 leetcode 1231.Divide Chocolate