【问题描述】
高二数学《课堂讲义》总共有n道题目要抄，编号1..n，抄每道题所花时间不一样，抄第i题要花 a[i] 分钟。由于 xxx还要准备IOI，显然不能成天写课堂讲义。xxx决定只用不超过 t 分钟时间抄这个，因此必然有空着的题。每道题要么不写，要么抄完，不能写一半。一段连续的空题称为一个空题段，它的长度就是所包含的题目数。这样应付自然会引起x老师的愤怒。x老师发怒的程度(简称发怒度)等于最长的空题段长度。
现在，xxx想知道他在这 t 分钟内写哪些题，才能够尽量降低x老师的发怒度。由于xxx很聪明，你只要告诉他发怒度的数值就可以了，不需输出方案。
【输入格式】
第一行为两个整数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
【样例解释】
分别写第4，6，10，14题，共用时 2+3+3+3=11 分钟。空题段：1-3(长为3)，5-5(长为1)，7-9(长为3)，11-13(长为3)，15-17(长为3 )。 所以发怒度为3。可以证明，此数据中不存在使得发怒度<=2的作法。
【数据范围】
30%数据 n<=2000，0
void solve() { int x=1,y=n,ans=n; while(x<=y) { int m=(x+y)/2; run(m); long long tmp=//空题段不超过m的情况下，完成题目所需的最小时间; if(tmp>t)//完成不了 x=m+1; else { y=m-1; ans=m; } } printf("%d",ans); }现在的关键是处理 tmp，即空题段不超过m的情况下，完成题目所需的最小时间; 这里可以采用dp 方程： //f(i)表示在前i道题中必选择第i道题做 && 最小空题段数不超过m时 的最小时间 //f(i)=min{f(j) || i-m-1<=j<=i-1}+a[i]
朴素的dp：
//solve30 //f(i)表示在前i道题中必选择第i道题做 && 最小空题段数不超过m时 的最小时间 //f(i)=min{f(j) || i-m-1<=j<=i-1}+a[i] #include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<queue> using namespace std; const long long inf=40000000000000005; int n,t; int a[100005]; long long f[100005]; void run(int m) {//f(i)=min{f(j) || i-m-1<=j<=i-1}+a[i] f[0]=0; for(int i=1;i<=m;i++) f[i]=a[i]; for(int i=m+1;i<=n+1;i++) f[i]=inf; long long t; for(int i=1;i<=n+1;i++) { t=inf; for(int j=i-m-1;j<=i-1;j++) { t=min(t,f[j]); } f[i]=t+a[i]; } } void solve() { int x=1,y=n,ans=n; while(x<=y) { int m=(x+y)/2; run(m); long long tmp=f[n+1];//空题段不超过m的情况下，完成题目所需的最小时间; if(tmp>t)//完成不了 x=m+1; else { y=m-1; ans=m; } } printf("%d",ans); } int main() { // freopen("in.txt","r",stdin); scanf("%d%d",&n,&t); for(int i=1;i<=n;i++) scanf("%d",&a[i]); a[n+1]=0; solve(); return 0; }时间复杂度分析：O（n * n *log2 n） 显然不能通过全部数据。 分析方程 f(i)=min{f(j) || i-m-1<=j<=i-1}+a[i] 实际上实在窗口长度为m时找一个f(j)的最小值，因此可以用单调序列优化。
//solve100
void run(int m) {//f(i)=min{f(j) || i-m-1<=j<=i-1}+a[i] f[0]=0; for(int i=1;i<=m;i++) f[i]=a[i]; for(int i=1;i<=n+1;i++) f[i]=inf; long long t; rear=0,front=0; q[rear++]=(data){0,0}; for(int i=1;i<=n+1;i++) { while(front!=rear && i-q[front].id-1>m) front++; f[i]=q[front].v+a[i]; while(front!=rear && q[rear-1].v>f[i]) rear--; q[rear++]=(data){f[i],i}; } }时间复杂度：O（n*log2 n *log2 n）(每个数据进队一次出队一次)
