wqs二分

应用

有\(n\)个物品，要求你选出 \(m\) 个，选的时候带有限制，要你求出最优的方案。

P1484

不带限制求解可以用\(dp\).

设\(f[i][0/1]\)表示当前为第\(i\)个坑，选或不选时的最大获利，\(g[i][0/1]\)为对应\(f[i][0/1]\)的最小挖坑次数。

那么我们只要判断最大获利时的最小次数是否满足\(\leq m\)即可二分。

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=5e5+10,INF=0x3f3f3f3f;
int a[N],f[N][2],g[N][2];
int n,m,maxn,ans,cnt;
bool check(int k){
    //memset(f,0,sizeof f),memset(g,0,sizeof g);
    f[0][0]=f[0][1]=g[0][0]=g[0][1]=0;
    for(int i=1;i<=n;++i){
        if(f[i-1][0]>f[i-1][1] || (f[i-1][0]==f[i-1][1] && g[i-1][0]<g[i-1][1])) f[i][0]=f[i-1][0],g[i][0]=g[i-1][0];
        else f[i][0]=f[i-1][1],g[i][0]=g[i-1][1];
        f[i][1]=f[i-1][0]+a[i]-k,g[i][1]=g[i-1][0]+1;   
    }
    ans=-INF,cnt=0;
    if(f[n][0]>f[n][1] || (f[n][0]==f[n][1] && g[n][0]<g[n][1])) ans=f[n][0],cnt=g[n][0];
    else ans=f[n][1],cnt=g[n][1];
    return cnt<=m;
}
signed main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
    if(check(0)){
        printf("%lld",ans);return 0;
    }
    int l=0,r=INF,res=0;
    while(l<=r){
        int mid=l+r>>1;
        if(check(mid)) res=ans+m*mid,r=mid-1;
        else l=mid+1;
    }
    printf("%lld",res);
    return 0;
}