牛吃草
居然真的是牛吃草
Description
由于现代化进程的加快，农场的养殖业也趋向机械化。
lyz 决定购置若干台自动喂草机来减少自己每天的工作量。为了简化问题，lyz 决定将草地建模成一条线段，总长为 \(n\)，即共有\(n\) 个单位长度，编号从左至右为 \(1∼n\)。
lyz 可以在每个单位长度独立选择是否放置一台自动喂草机。由于场地的限制，喂草机一旦在 \(i\) 处放下，它只能往左边延伸覆盖一个从 \(i\) 开始的完整区间，且延伸的距离不能超过 \(w_i\) ，即最多到编号为 \(i-w_i+1\) 的单位长度。同时为了小草的健康着想，营养不能太丰富，因此每个单位长度只能被一台自动喂草机覆盖。
lyz 想使得每台喂草机的覆盖大小达到一个最低标准以节省费用，若喂草机覆盖 $ [l,r] $ ，那么覆盖大小为 \(r-l+1\) 。他规定一台喂草机最小覆盖大小为 \(size\) 。所以如果一台喂草机的覆盖大小\(< size\)，说明这个位置不能放置喂草机。
现在，lyz 想知道，如果喂草机覆盖的总大小仅需达到草地总长的 \(s \%\)，最小覆盖大小最大是多少？
Input
输入共三行。
第一行输入整数 n。
第二行输入n 个整数 \(w_i\) ，表示第 i个位置的延伸距离不能达到 \(w_i\)。
最后一行给定整数 s，意义如上述所示。
Output
输出最大的 size，意义如上述所示。
Samples
4
1 2 3 4
100
4
样例解释1
最小覆盖最大值就为 4，在第四个位置放喂草机即可。
5
5 4 2 3 2
50
3
样例解释2
在第四个位置放喂草机，可以覆盖 3 个位置，覆盖率达到 50% 以上。
数据范围
对于 100%的数据，$1\le s \le 100,2\le i\le n, w_{i-1}\ge w_i-1 $
正解
二分+单调队列优化DP
一眼就可以看出是二分答案 (所以半眼是看不出来的
注意审题，赛时一车人读假题目了，喂草机最大范围是 \(w_i\) ，可以小于这个值，因此最后结果不一定在 \(w_i\) 中取，另外二分左端点应该从1开始。
二分答案 size ，然后检查答案是否可行，求当前 size 最大的覆盖面积与 \(s\%\) 比较。check函数用DP实现。
朴素DP
令 \(f_i\) 为前 \(i\) 个草坪能覆盖的最大面积，对于 \(f_i\) 可能放也可能不放。
如果放置喂草机，对覆盖面积没有影响， $f_i=f_{i-1} $
如果不放，考虑可能的转移来源， \(i\) 的最大覆盖面积为 \(w_i\) ，转移的左端点应该是 $i-w_i $ ，又因为覆盖面积不能小于size，转移的右端点是 $i-size $ 。得到方程：
\[f_i= \max_{i-w_i \le j \le i-size} \{ f_j+i-j \} \]单调队列优化
上述做法显然是会T的，考虑优化。
注意到数据范围中至关重要的一点
\[w_{i-1} \ge w_i-1 \]这是解决整个题目的关键 (不知多少人没看见呢)
仔细想想 \(w_i\) 决定了DP转移区间的左端点，而上述条件保证的是这个左端点不会因 \(i\) 增大而减小，即左端点的下标单调不下降，自然而然想到单调队列。
调整一下方程
\[f_i= \max_{i-w_i \le j \le i-size } \{ (f_j-j)+i \} \]对于 \(f_i\) ，方程中的 \(i\) 是一定的，用单调队列维护 $ f_j-j $
注意 \(f_j-j\) 进入单调队列的时间，并不是刚刚计算 \(f_j\) 就进队列，而是对于每一个可行的 \(i\) ，将 $ f_{i-x}-(i-x) $ 压入队列。
这样做是因为本题对转移的左右端点均有限制，直接 $ push _ back （f_j-j） $ 可能导致某些 $f_k(j<k<i) $ 右端点不符合要求
另外一点，如果双端队列在check函数里定义，一定要清空，否则队列里会有其他元素。
Code
#include<bits/stdc++.h>
using namespace std;
const int N=6e5;
int n,w[N],s,maxn,minn=1e8,dp[N],ans;
deque<int>q;
bool check(int x){
memset(dp,0,sizeof(dp));
int p=0;
q.clear( ) ;
for(int i=1;i<=n;i++){
if(i>=x){
while(!q.empty()&&dp[i-x]-(i-x)+n>dp[q.back()]-q.back()+n)
q.pop_back();
q.push_back(i-x);
}
dp[i]=max(dp[i],dp[i-1]);
while(!q.empty()&&i-q.front()>w[i])q.pop_front();
if(!q.empty()) dp[i]=max(dp[q.front()]+(i-q.front()),dp[i]);
p=max(p,dp[i]);
}
if(p>=((s*n+99)/100))return 1;
else return 0;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&w[i]);
maxn=max(maxn,w[i]);
minn=min(minn,w[i]);
}
scanf("%d",&s);
int l=1,r=maxn;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid))l=mid+1;
else r=mid-1;
}
printf("%d",r);
}