《思远高考绿色通道》(Green Passage, GP)是唐山一中常用的练习册之一，其题量之大深受lsz等许多oiers的痛恨，其中又以数学绿色通道为最。2007年某月某日，soon-if (数学课代表)，又一次宣布收这本作业，而lsz还一点也没有写……

高二数学《绿色通道》总共有n道题目要写(其实是抄)，编号1..n，抄每道题所花时间不一样，抄第i题要花a[i]分钟。由于lsz还要准备NOIP，显然不能成天写绿色通道。lsz决定只用不超过t分钟时间抄这个，因此必然有空着的题。每道题要么不写，要么抄完，不能写一半。一段连续的空题称为一个空题段，它的长度就是所包含的题目数。这样应付自然会引起马老师的愤怒。马老师发怒的程度(简称发怒度)等于最长的空题段长度。

现在，lsz想知道他在这t分钟内写哪些题，才能够尽量降低马老师的发怒度。由于lsz很聪明，你只要告诉他发怒度的数值就可以了，不需输出方案。(快乐融化：那么lsz怎么不自己写程序？lsz：我还在抄别的科目的作业……)

第一行为两个整数n,t，代表共有n道题目，t分钟时间。

以下一行，为n个整数，依次为a[1], a[2],... a[n]，意义如上所述。

仅一行，一个整数w，为最低的发怒度。

17 11

6 4 5 2 5 3 4 5 2 3 4 5 2 3 6 3 5

3

60%数据 n<=2000

100%数据 0<n<=50000，0<a[i]<=3000，0<t<=100000000

暴力74分

测试点#gp1.in  结果:AC    内存使用量:  492kB     时间使用量:  0ms     
测试点#gp10.in  结果:AC    内存使用量:  492kB     时间使用量:  4ms     
测试点#gp11.in  结果:AC    内存使用量:  488kB     时间使用量:  0ms     
测试点#gp12.in  结果:AC    内存使用量:  492kB     时间使用量:  1ms     
测试点#gp13.in  结果:AC    内存使用量:  492kB     时间使用量:  0ms     
测试点#gp14.in  结果:AC    内存使用量:  488kB     时间使用量:  0ms     
测试点#gp15.in  结果:AC    内存使用量:  488kB     时间使用量:  0ms     
测试点#gp16.in  结果:AC    内存使用量:  488kB     时间使用量:  0ms     
测试点#gp17.in  结果:AC    内存使用量:  492kB     时间使用量:  0ms     
测试点#gp18.in  结果:AC    内存使用量:  492kB     时间使用量:  4ms     
测试点#gp19.in  结果:AC    内存使用量:  360kB     时间使用量:  1ms     
测试点#gp2.in  结果:AC    内存使用量:  492kB     时间使用量:  0ms     
测试点#gp20.in  结果:AC    内存使用量:  488kB     时间使用量:  0ms     
测试点#gp21.in  结果:AC    内存使用量:  492kB     时间使用量:  0ms     
测试点#gp22.in  结果:AC    内存使用量:  492kB     时间使用量:  0ms     
测试点#gp23.in  结果:AC    内存使用量:  492kB     时间使用量:  4ms     
测试点#gp24.in  结果:AC    内存使用量:  488kB     时间使用量:  0ms     
测试点#gp25.in  结果:AC    内存使用量:  488kB     时间使用量:  0ms     
测试点#gp26.in  结果:AC    内存使用量:  488kB     时间使用量:  0ms     
测试点#gp27.in  结果:AC    内存使用量:  488kB     时间使用量:  1ms     
测试点#gp28.in  结果:AC    内存使用量:  488kB     时间使用量:  0ms     
测试点#gp29.in  结果:AC    内存使用量:  492kB     时间使用量:  0ms     
测试点#gp3.in  结果:AC    内存使用量:  492kB     时间使用量:  3ms     
测试点#gp30.in  结果:AC    内存使用量:  488kB     时间使用量:  4ms     
测试点#gp31.in  结果:AC    内存使用量:  488kB     时间使用量:  27ms     
测试点#gp32.in  结果:AC    内存使用量:  492kB     时间使用量:  763ms     
测试点#gp33.in  结果:TLE    内存使用量:  616kB     时间使用量:  1000ms     
测试点#gp34.in  结果:TLE    内存使用量:  620kB     时间使用量:  1000ms     
测试点#gp35.in  结果:TLE    内存使用量:  620kB     时间使用量:  1000ms     
测试点#gp36.in  结果:TLE    内存使用量:  616kB     时间使用量:  1000ms     
测试点#gp37.in  结果:AC    内存使用量:  364kB     时间使用量:  503ms     
测试点#gp38.in  结果:TLE    内存使用量:  616kB     时间使用量:  1000ms     
测试点#gp39.in  结果:AC    内存使用量:  492kB     时间使用量:  19ms     
测试点#gp4.in  结果:AC    内存使用量:  492kB     时间使用量:  4ms     
测试点#gp40.in  结果:TLE    内存使用量:  620kB     时间使用量:  1000ms     
测试点#gp41.in  结果:TLE    内存使用量:  620kB     时间使用量:  1000ms     
测试点#gp42.in  结果:AC    内存使用量:  492kB     时间使用量:  382ms     
测试点#gp43.in  结果:TLE    内存使用量:  616kB     时间使用量:  1000ms     
测试点#gp44.in  结果:TLE    内存使用量:  616kB     时间使用量:  1000ms     
测试点#gp45.in  结果:TLE    内存使用量:  616kB     时间使用量:  1000ms     
测试点#gp46.in  结果:AC    内存使用量:  492kB     时间使用量:  322ms     
测试点#gp47.in  结果:TLE    内存使用量:  620kB     时间使用量:  1000ms     
测试点#gp48.in  结果:TLE    内存使用量:  620kB     时间使用量:  1000ms     
测试点#gp49.in  结果:TLE    内存使用量:  616kB     时间使用量:  1000ms     
测试点#gp5.in  结果:AC    内存使用量:  488kB     时间使用量:  1ms     
测试点#gp50.in  结果:AC    内存使用量:  492kB     时间使用量:  826ms     
测试点#gp6.in  结果:AC    内存使用量:  488kB     时间使用量:  0ms     
测试点#gp7.in  结果:AC    内存使用量:  492kB     时间使用量:  6ms     
测试点#gp8.in  结果:AC    内存使用量:  492kB     时间使用量:  0ms     
测试点#gp9.in  结果:AC    内存使用量:  488kB     时间使用量:  0ms     

#include<iostream>#include<cstdio>#include<cstring>#define maxn 50001using namespace std;int n,t,ans;int f[maxn],a[maxn];bool check(int mid){    memset(f,127/3,sizeof f);    f[0]=0;    for(int i=1;i<=n;i++)      for(int j=max(i-mid-1,0);j<i;j++)        f[i]=min(f[i],f[j]+a[i]);    ans=0x3f3f3f3f;    for(int i=n-mid-1;i<=n;i++)        ans=min(ans,f[i]);    return ans<=t;      }int main(){    scanf("%d%d",&n,&t);    for(int i=1;i<=n;i++)      scanf("%d",&a[i]);    int l=0,r=n;    while(l<r)    {        int mid=(l+r)>>1;        if(check(mid))          r=mid;        else l=mid+1;    }    printf("%d\n",l);    return 0;}

心若向阳，无言悲伤

AC

/*用f[i]表示在做第i道题的情况下，前i道题在合法状况下（即空题段长度不超过mid）可能的所有方案中的最小时间那么转移方程为 f[i]=min(f[j])+a[i];其中j的范围是i-mid-1<=j<=i-1 这是因为我们保证a[i]入选，且由于最大空时段为mid枚举j应当从i之前不做mid个的前面那一道题开始由于每个f[j]内的状态必然是合法的最小值，也就是最长空时段不超过mid的最小值，而j又一定被选中（做这道题），最终方案也一定是合法的。*/#include<iostream>#include<cstdio>#include<cstring>#define maxn 50010using namespace std;int n,m,ans,t;int a[maxn],f[maxn],q[maxn];bool check(int mid){    memset(f,127/3,sizeof f);    f[0]=0;    int l=0,r=0;    q[r++]=0;    for(int i=1;i<=n;i++)    {        while(l<=r&&q[l]<i-mid-1) l++;//删除队列头部所有位置小于查询起始位置的数字        f[i]=f[q[l]]+a[i];//查询修改后的头元素（最小元素）         while(l<=r&&f[q[r]]>=f[i]) r--;//删除队列尾部所有耗时比当前元素大的元素        q[++r]=i;    }    /*        等价于f[i]=最小的f[j]+a[i];        i跟j之间空着一段mid 所以j就是i-mid-1    */    int ans=0x3f3f3f3f;    for(int i=n-mid-1;i<=n;i++)        ans=min(ans,f[i]);    return ans<=t;}int main(){    scanf("%d%d",&n,&t);    for (int i=1;i<=n;i++)       scanf("%d",&a[i]);    int l=0,r=n;    while(l<r)    {        int mid=(l+r)>>1;        if(check(mid))          r=mid;        else l=mid+1;    }    printf("%d\n",l);    return 0;}