【分果果——DP（困难）】

题目

分析

分果果题解参考，下面是补充https://blog.csdn.net/AC__dream/article/details/129431299

关于状态

设f[i][j][k]表示第i个人取到的最后一个糖果编号是j，第i-1个人取到的最后一个糖果编号小于等于k时的最大重量的最小值

关于转移方程

关于 j >= k 的必然性  区间不包含的必然性

代码

#include <bits/stdc++.h>
using namespace std;const int N = 110;int n, m;
int f[N][N][N], a[N], s[N];
bool st[N * N];int main()
{cin >> n >> m;for (int i = 1; i <= n; i++){cin >> a[i];s[i] = a[i] + s[i - 1];for(int j = 0; j < i; j++)st[s[i] - s[j]] = 1;}int ans = 0x3f3f3f3f;for (int mn = 1; mn * m <= 2 * s[n]; mn++){if(!st[mn]) continue;memset(f, 0x3f, sizeof f);f[0][0][0] = 0;for (int i = 1; i <= m; i++){for (int k = 0; k <= n; k++){int p = 0; //题解里这里是id不是pfor (int j = k; j <= n; j++){if(s[j] < mn) continue;while (p < k && s[j] - s[p] > mn) p++;if (s[j] - s[p] < mn)p--;if(k) f[i][j][k] = f[i][j][k - 1];f[i][j][k] = min(f[i][j][k], max(f[i - 1][k][p], s[j] - s[p]));}}}ans = min(ans, f[m][n][n] - mn);}cout << ans;
}