问题

给定n个整数ai组成的序列，现在要求将序列分割为m段，每段子序列中的数在原序列中连续排列。如何分割才能使这m段子序列的和的最大值达到最小？ 例如：给定序列：5 4 3 2 1，n=5, m=3，可分为 5 ' 4 ' 3 2 1，其子序列和的最大值为最后一段，为6。

代码

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int dp[5000][5000];

int MAX(int n1, int n2) {

    if (n1 < n2)
        return n2;
    else
        return n1;
}

void calculate(int a[], int n, int m) {

    int i, j, k, temp, min;

    for (i = 1; i <= n; i++) {

        dp[i][1] = dp[i - 1][1] + a[i];

        for (j = 2; j <= m; j++) {

            min = 99999;

            for (k = 1; k <= i; k++) {

                temp = MAX(dp[k][j - 1], dp[i][1] - dp[k][1]);

                if (temp < min) {
                    min = temp;
                }
            }

            dp[i][j] = min;
        }
    }
    printf("%d", dp[n][m]);
}

int main()
{
    int a[5000];
    int i, n, m;

    scanf("%d", &n);

    scanf("%d", &m);

    for (i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }

    calculate(a, n, m);
    return 0;
}

样例

• 对于100%的数据，1≤ n ≤5000，1≤ m ≤100,_ai ​≤ 100 且 m ≤ n

输入

*第1行整数n和m。 第2行为n个数

5 3
5 4 3 2 1

输出 (最小m段和)

6