先判断无解的情况。

由于每一段都要非 0 的偶数朵花，那么当 \(n\) 为奇数时显然无解。

用 \(m\) 个点固定，就是分成了 \(m-1\) 段。每个半段不能超过 \(d\) 朵，那么总数最多为 \(2 d \cdot (m-1)\)，最少为 \(2 \cdot m\)。所以当 \(n\) 大于最大值，小于最小值时，无解。

 

题目要求最小的半段重量的最大值，可以二分答案。我们定义 \(check(x)\) 为半段重量最大为 \(x\) 时，能否划分成 \(m-1\) 段。

可以用 DP 来判断。设 \(f_i\) 为前 \(i\) 朵花在满足限制的情况下最少分成多少段？不行。不难发现，奇数段只能从偶数段转移而来，偶数段只能从奇数段转移而来。不记录奇偶性的话会产生后效性。

所以设 \(f_{i,j}\) 为前 \(i\) 朵花在满足限制的情况下最少分成多少段，且段数奇数或偶数。当 \(j=0\) 时为偶数，\(j=1\) 时为奇数。

边界 \[ f_{i,j} = \begin{cases} 0 & i = j = 0 \\ \inf & otherwise \end{cases} \] 转移。这个就比较显然了。 \[ \begin{cases} f_{i,0} = \min{ \{ f_{j,1} + 1 \} } \\ f_{i,1} = \min{ \{ f_{j,0} + 1 \} } \end{cases} \] 其中 \([j+1,i]\) 这一段有偶数朵花且不超过 \(2d\)。

如果 \(m\) 是奇数，最终一定有偶数段，如果 \(m\) 是偶数，最终一定有奇数段。所以答案为 \(f_{n,(m-1) \% 2}\)。

具体实现中要考虑半段的变化，最好结合 pdf 里的图看看。

复杂度 \(O(n^2 \log_2 n)\)。

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define ll long long
const int N=4e4+6;
int t, n, m, d, s[N], f[N][2];
inline bool C(int x) {
    memset(f,0x7f,sizeof(f));
    f[0][0]=0;
    for(int i=2;i<=n;i+=2) for(int j=1;(j<=d)&&(j<=i/2);++j) {
    // 保证i是偶数。 j是半段长度，保证它不超过d与i/2
        if(s[i]-s[i-j]>x) break;
        // 靠后的半段超重了，随着j的增加它的重量单调增
        // 所有的j都不能满足条件了，所以直接跳过这个i
        if(s[i-j]-s[i-2*j]>x) continue;
        // 长度为j的半段超重了，但随着j的增加它会整体向后移动
        // 可能还有满足条件的半段，直接往后找
        f[i][0]=min(f[i][0],f[i-2*j][1]+1);
        f[i][1]=min(f[i][1],f[i-2*j][0]+1);
    }
    return f[n][(m-1)%2]<=m-1;
}
inline void sol() {
    s[0]=0;
    scanf("%d%d%d",&n,&m,&d);
    for(int i=1,w;i<=n;++i) {
        scanf("%d",&w);
        s[i]=s[i-1]+w;
    }
    if(n&1||n>2*d*(m-1)||n<2*(m-1)) { puts("BAD"); return; }
    int l=1, r=s[n], mid;
    while(l<r) {
        mid=(l+r)/2;
        if(C(mid)) r=mid; else l=mid+1;
    }
    printf("%d\n",l);
}
int main() { for(scanf("%d",&t);t--;sol()); }