（蓝桥真题）分果果（动态规划）

题目链接：P8746 [蓝桥杯 2021 省 A] 分果果 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

样例1输入： 

5 2
6 1 2 7 9

样例1输出：

0

样例2输入：

5 5
6 1 2 7 9

样例2输出：

2

分析：这道题的状态表示比较难想：首先我们先考虑一下有哪些东西需要维护：

1.当前分配到哪个小朋友

2.当前分配到的小朋友的糖果最小值

3.当前分配到的小朋友的糖果最大值

4.当前已经分配一次的糖果编号位置

5.当前已经分配两次的糖果编号位置

那么其中我们可以选择一个作为f数组的含义，其余的四个显然都需要枚举。我们可以考虑用f数组存储当前状态分配到的小朋友的糖果的最大值，那么我们就开始枚举剩余四个维度。

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

答案就是min(f[m][n][n]-mn)，所以我们要在mn一定的情况下尽可能减少f数组的值

首先要枚举的就是分配到的小朋友的糖果的最小值mn，那么我们每次考虑给小朋友分配一段连续的糖果区间就要注意区间和不能小于mn。

那么f[i][j][k]应该怎么更新呢？

首先有f[i][j][k]=f[i][j][k-1]，这个无需多言，由于f数组维护的最大值，那么从这个角度也可以看出随着k的增加f数组是非递增的

还有就是第i个人用了前i-1个人中已经分配两次糖果编号的后某个位置开始，不妨设为t

那么就有f[i][j][k]=max(f[i-1][k][t],s[j]-s[t]),s数组是前缀和

但是为了尽可能减少f数组的值，就要使得f[i-1][k][t]和s[j]-s[t]的值都尽可能小，我们可以发现，随着t的增大，这两个值都是在逐渐减小的，但是t也要有一个限制条件，就是因为我们给第i个人分配的糖果区间是[t,j]，所以这个区间内的糖果总数是要大于等于最小值mn的，所以这块我们可以。

有小伙伴可能会有疑问，为什么不能是从前i-1个人中已经分配一次糖果编号的后一个位置开始呢？这个是包含在上述情况的，因为分配两次糖果编号的位置一定是小于分配一次糖果编号的位置的，所以我们从分配两次糖果编号的位置开始分配总有一次会使得编号位置大于分配一次糖果编号的位置，这个时候原来的分配一次编号的位置就变为了分配两次编号的位置了，那么也就变成上述情况了。

还有就是从上面的分析，我们可以发现每次从分配两次的编号后面的某个位置t开始继续分配，此次分配后的位置都是大于等于分配一次的编号的位置，有没有可能是小于第一次分配编号的位置呢？这个是不可能的，因为如果小于第一次编号分配的位置，那么说明上次分配的区间是包含本次分配的区间的，那么我们完全可以把这两次分配调整为相交但不包含的情况，这样两个区间的最大值一定会减少，由于答案是最大值减去最小值，所以对答案也只会更优

其他就是一些细节上的问题了，可以看下代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=103;
int f[N][N][N],w[N],s[N];
/*
f[i][j][k]表示第i个人取到的最后一个糖果编号是j，第i-1
个人取到的最后一个糖果编号小于等于k时的最大重量的最小值 
*/
bool vis[N*N];//vis[i]记录存在一段区间满足区间和为i
int main()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++){scanf("%d",&w[i]);s[i]=s[i-1]+w[i];for(int j=0;j<i;j++)vis[s[i]-s[j]]=true;}int ans=0x3f3f3f3f;for(int mn=1;mn*m<=2*s[n];mn++)//枚举重量最小值 {if(!vis[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++)//枚举第i-1个人选的最后一个糖果编号{int id=0;//找到第i-2个人选的最后一个糖果编号for(int j=k;j<=n;j++)//第i个人选的最后一个糖果编号 { if(k>0) f[i][j][k]=f[i][j][k-1];if(s[j]<mn) continue;//每个人选取的最小重量不能小于mn//第i个人选的区间是[id+1,j]while(id<k&&s[j]-s[id]>mn) id++;if(s[j]-s[id]<mn) id--;f[i][j][k]=min(f[i][j][k],max(f[i-1][k][id],s[j]-s[id]));}}ans=min(ans,f[m][n][n]-mn); }printf("%d",ans);return 0;
}