题目链接

咳咳咳，第一次没大看题解做DP

以前的我应该是这样的

哇咔咔，这tm咋做，不管了，先看个题解，再写代码

终于看懂了，卧槽咋写啊，算了还是抄吧

第一问类似于noip的那个跳房子，随便做

这里重点讲第二问

首先，不会做，那就先写暴力

dp当然得写dp暴力了

\(f[k][i]\) 表示选择了k段,到了第i个位置(一共有m+1段)

状态转移方程就是$$f[k][i]=f[k][i]+f[k-1]j$$

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

    if(sum[i]<=ans)

        f[1][i]=1;

}

for (int k=2;k<=m+1;++k) {

    for(int i=k;i<=n;++i) {

        for(int j=i;j>=1;--j) {

            if(sum[i]-sum[j-1] <= ans) {

                f[k][i] += f[k-1][j];

            }

        }

    }

}

三重循环，第一重枚举k,第二重枚举i，第三重枚举j

好了，时间复杂度\(O(n^{2}*m)\),空间复杂度\(O(n*m)\)，\(TLE\)(太不良心了，不给暴力分)

空间复杂度的话，很明显可以滚动数组

考虑第三重循环，是上一次转移的一段连续的区间

那么，我们是不是可以把上一他们都前缀和，然后O(1)

那前缀和范围不明确咋办?

我们可以用数组O(n)预处理出来

很明显的 $i>j 则p[i]>=p[j] $，指针从1一直往后挪，挪到n

时间复杂度\((n*m)\),空间复杂度\(O(n)\),优秀_(≧▽≦)/

最后，注意边界吧

/**************************************************************

    Problem: 1044

    User: 3010651817

    Language: C++

    Result: Accepted

    Time:4528 ms

    Memory:11052 kb

****************************************************************/

#include <iostream>

#include <cstdio>

using namespace std;

const int maxn = 5e5 + 7;

const int mod = 10007;

int a[maxn], n, m, l, r;

int sum[maxn], p[maxn];

bool check(int x) {

    int js = 0, tot = 0;

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

        if (tot + a[i] > x) {

            js++, tot = 0;

        }

        tot += a[i];

    }

    if (tot > x) return 0;

    return m >= js;

}

int f[2][maxn];

int main() {

    scanf("%d%d", &n, &m);

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

        scanf("%d", &a[i]), sum[i] = sum[i - 1] + a[i];

    r = sum[n];

    int ans = 0;

    while (l <= r) {

        int mid = (l + r) >> 1;

        if (check(mid)) ans = mid, r = mid - 1;

        else l = mid + 1;

    }

    p[1] = 1;

    for (int i = 2; i <= n; ++i) {

        p[i] = p[i - 1];

        while (sum[i] - sum[p[i] - 1] > ans && p[i] <= i) {

            p[i]++;

        }

    }

    for (int i = 1; i <= n; ++i) p[i] = p[i] >= 2 ? p[i] - 2 : 0;

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

        if (sum[i] <= ans) {

            f[1][i] = 1;

        }

        f[1][i] = f[1][i - 1] + f[1][i];

    }

    int tot = 0;

    for (int i = 2, cnt = 0; i <= m + 1; ++i, cnt ^= 1) {

        for (int j = i; j <= n; ++j) {

            f[cnt][j] = ((f[cnt][j - 1] + f[cnt ^ 1][j - 1]) % mod + mod - f[cnt ^ 1][p[j]]) % mod;

        }

        tot = ((tot + f[cnt][n]) % mod + mod - f[cnt][n - 1]) % mod;

    }

    printf("%d %d\n", ans, tot );

    return 0;

}