[DP][二分][经典][×] UVA 1443 Garlands

没做出来看题解的时候就在想出题人是怎么搞出来的。。。这个做法emm

最大值最小化肯定要想二分，但是二分后这题目怎么check是个技术活。我最悲催的是理解错了题目意思，以为这些珠子（不管是什么吧我感觉是珠子）可以互换位置。实际上是不可以换的emm所以说看题还是要好好搞明白。

然后说说这个check，这个一开始有点迷，因为它本身是dp那一章的题，但是二分的check一般都是判断一个可行性，那加了这个二分出来的答案的约束怎么判断可行性？首先可以确定一般dp不会说去dp那种“区间上的最大值”之类的东西，他要做一定是一个量化的东西去求最优解。这里的话可以想象一下，如果用了比m更少的段就可以满足要求那么就可以继续进行下去？这样的话必须保证段数和最紧的上限是一个正比的关系！但是算一算可以发现并没有这种正比关系，一般这时候就放弃用二分的方法了，但是这个题最精彩的地方就在于他的奇偶性，由于题目本身一直在要求“半段”，所以可以利用奇偶性来保证正比单调，具体可以看这位dalao的博客

#include<bits/stdc++.h>

using namespace std;
const int maxn=4e4+15;
const int INF=0x3f3f3f3f;

int wt[maxn];
int dp[maxn][2];
int psum[maxn];
int d,n,m;
bool check(int x)
{
    memset(dp,INF,sizeof(dp));dp[0][0]=0;
    for(int i=2;i<=n;i+=2)
        for(int j=i-1;j>=1&&(i-j+1)<=2*d&&psum[i]-psum[(i+j)>>1]<=x;j-=2)
            if(psum[(i+j)>>1]-psum[j-1]<=x)
                dp[i][0]=min(dp[i][0],dp[j-1][1]+1),dp[i][1]=min(dp[i][1],dp[j-1][0]+1);
    return ((m-1)%2)?(dp[n][1]<m):(dp[n][0]<m);
}

int main()
{
    int t,L,R,M;
    scanf("%d",&t);
    while(t--)
    {
        L=R=0;
        scanf("%d%d%d",&n,&m,&d);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&wt[i]);L=min(L,wt[i]),R+=wt[i];
        }
        if(2*d*(m-1)<n||n<2*(m-1)||n%2)
        {
            printf("BAD\n");continue;
        }
        R=((R+1)>>1);
        for(int i=1;i<=n;i++)
            psum[i]=psum[i-1]+wt[i];
        while(L<R)
        {
            M=(L+R)>>1;
            if(check(M))
                R=M;
            else
                L=M+1;
        }
        printf("%d\n",L);
    }
    return 0;
}