题意：给你n个数代表重量，让你分成连续的m-1段，每一段的一半长不能超过d，求所有段中，半段最重的最小值
思路：求最大值的最小值，显然是二分的节奏，但这不完全是搜索啊，还有涉及到DP，
那么为了能够用来二分的check，又要用到我们搜索的值，也就是最小值x，如果这n个数能都分成m-1,且按条件不超过x，注意的是其实只要不大于m-1的话都是证明这个数x成立的，所以可以用dp[i][2]表示前i个不超过x的最小段数，只要这个最小的段数不超过m-1,就证明这个是可以的，又增加一维来表示段数是奇偶的情况，便于转移
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 40005;
const int INF = 0x3f3f3f3f;
int w[MAXN],sum[MAXN];
int dp[MAXN][2],n,m,d;
int check(int x){
dp[0][0] = 0;
dp[0][1] = INF;
for (int i = 2; i <= n; i += 2){
dp[i][0] = INF;
dp[i][1] = INF;
for (int len = 1; len <= d && i-2*len >= 0; len++){
if (sum[i]-sum[i-len] > x)
break;
if (sum[i-len] - sum[i-2*len] <= x){
dp[i][0] = min(dp[i][0],dp[i-2*len][1]+1);
dp[i][1] = min(dp[i][1],dp[i-2*len][0]+1);
}
}
}
if (dp[n][(m-1)%2] > m-1)
return 0;
else return 1;
}
int main(){
int t;
scanf("%d",&t);
while (t--){
scanf("%d%d%d",&n,&m,&d);
sum[0] = 0;
for (int i = 1; i <= n; i++){
scanf("%d",&w[i]);
sum[i] = sum[i-1] + w[i];
}
if ((n & 1) || (n < 2*(m-1)) || (n > 2*d*(m-1)))
printf("BAD\n");
else {
int l = 1,r = sum[n];
while (l < r){
int mid = (l+r) >> 1;
if (check(mid))
r = mid;
else l = mid + 1;
}
printf("%d\n",l);
}
}
return 0;
}