Complete Partition Of Array
1.分成sum相等的k份
若,顯然預處理,然後掃一遍枚舉分界點即可。
若,可以預處理字尾。
然後枚舉第一個分界點,求和即可。
當然也可以使用雙指針思路類似。
當,但不是很大時,可以考慮。
區間和可以預處理字首和、差分計算。
時間複雜度:
1.1 Bouns
當
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
傳送門