codevs3342

思路：

既然是要求最小化最长空题段，直接二分答案。然后就是check函数的写法。

先考虑n方转移，假设当前二分的答案是x，用f[i]表示前i个题，第i道题写的最小花费时间。最后再去判断后f数组的后x个值是否小于等于要求时间的。然后返回。

int check(int x) {
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    for(int i=1;i<=n;++i)
        for(int j=i-1;j>=0&&j>=i-x-1;--j)
            f[i]=min(f[i],f[j]+a[i]);
    for(int i=n;i>=n-x;--i)
        if(f[i]<=t) return 1;
    return 0;
}

然后考虑优化这个dp，可以发现每个f[i]都是从前面x个值中的最小值转移过来的，可以用单调队列维护。

int check(int x) {
    Head=1,Tail=1;
    f[0]=0;
    q[1]=0;
    for(int i=1;i<=n;++i) {
        while(q[Head]<i-x-1&&Head<=Tail) Head++;
        f[i]=f[q[Head]]+a[i];
        while(f[q[Tail]]>=f[i]&&Tail>=Head) Tail--;
        q[++Tail]=i;
    }
    return f[q[Head]]<=t;
}

代码

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=50000+100;
int f[N];//f[i]表示前i道题，第i道题做的最小花费时间 
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int n,t;
int a[N];
int q[N],Head,Tail;
int check(int x) {
    Head=1,Tail=1;
    f[0]=0;
    q[1]=0;
    for(int i=1;i<=n;++i) {
        while(q[Head]<i-x-1&&Head<=Tail) Head++;
        f[i]=f[q[Head]]+a[i];
        while(f[q[Tail]]>=f[i]&&Tail>=Head) Tail--;
        q[++Tail]=i;
    }
    return f[q[Head]]<=t;
}
int main() {
    n=read(),t=read();
    for(int i=1;i<=n;++i) a[i]=read();
    int ans=0,l=0,r=n;
    while(l<=r) {
        int mid=l+r>>1;
        if(check(mid)) r=mid-1,ans=mid;
        else l=mid+1;
    }
    cout<<ans;
    return 0;
}