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

​​傳送門​​