初三年后集训测试 $T 2 $ 牛吃草
一言难尽
$ Description $
由于现代化进程的加快，农场的养殖业也趋向机械化。
\(QZS\) 决定购置若干台自动喂草机来减少自己每天的工作量。为了简化问题，\(QZS\) 决定将草地建模成一条线段，总长为 \(n\) ，即共有 \(n\) 个单位长度，编号从左至右为 $ 1 \dots n $ 。
\(QZS\) 可以在每个单位长度独立选择是否放置一台自动喂草机。由于场地的限制，喂草机一旦在 \(i\) 处放下，它只能往左边延伸覆盖一个从 \(i\) 开始的完整区间，且延伸的距离不能超过 \(w_i\)
，即最多到编号为 $ i - w[ i ] + 1 $
的单位长度。同时为了小草的健康着想，营养不能太丰富，因此每个单位长度只能被一台自动喂草机覆盖。
\(QZS\) 想使得每台喂草机的覆盖大小达到一个最低标准以节省费用，若喂草机覆盖 $ [ l , r ] $
，那么覆盖大小为 $ [ r - l + 1 ] $
。他规定一台喂草机最小覆盖大小为 \(size\) 。所以如果一台喂草机的覆盖大小 \(<size\) ，说明这个位置不能放置喂草机。
现在，\(QZS\) 想知道，如果喂草机覆盖的总大小仅需达到草地总长的 \(s\%\)，最小覆盖大小最大是多少？
\(Input\)
输入共三行。
第一行输入整数 \(n\) 。
第二行输入 \(n\) 个整数
，表示第 \(i\) 个位置的延伸距离不能达到
。
最后一行给定整数 \(s\) ，意义如上述所示。
\(Output\)
输出一个整数 \(Size\) ，意思同上
（注意： \(size\) 并非从 \(w_i\) 中取值 ）
数据大小
$1 \le s \le 100 , 2 \le i \le n , \color{red}w_{ i - 1 } \geq w_i - 1 $
题解
·暴力
首先一眼的 \(二分答案\) ， 然后在 \(Check\) 函数里考虑 \(DP\) .
问题是怎么 \(DP\)
首先考虑定义个 \(DP\) 数组,表示前 \(i\) 个中,最小的最大 \(size\) .
那么二分的是你最后的输出的答案。
枚举 \(j\) 为前端节点，则转移方程为：
\[dp_{ i } = \max( \ dp_{ i - 1 } , dp_{ j } + i - j \ ) ( i - j \ge mid \ 且 \ i - j \le w_i ) \]时间复杂度为 \(O(\ n^2\times logn \ )\) 由于数据水的 \(原\) (神) \(因\) ， 本题可拿 \(\color{green}95pts\)
·正解
·正解是什么
下面讲一下正解之 \(---\) 单调队列优化 \(DP\) .
观察上方标红的数据大小的位置。（四非常纵要滴）
他的意义是什么捏？
给他转化一下，得到的意思是：
第 $ i $ 个位置可以控到的最左端 ， 永远小于等于第 $ i - 1 $ 个位置的可以控到的最左端.
那么他的意思就很明确了。
你的右端点最后返回的 \(DP\) 值，一定是从某个左端点转移过来的。
你想一想在你跑单队的过程中，是不是如果你现在队顶的元素不符合条件的话，那么就让他滚出队列？
假设第 \(i\) 个数的左端点是在第 $ i - 1 $ 的左端点的左边的话，那么这个由于你在枚举第 $ i - 1 $ 个元素时，
第 \(i\) 个元素的左端点就被排出去了。单队，寄。
但现在，他给了个这么优秀的条件，不打单队对不起他。
·正解怎么做
首先，使用二分答案，左端点是1，右端点是 \(w_{ max }\)
然后的话，在 \(Check\) 函数里，调用 \(DP\)
使单调队列维护的是 $ dp[ \ l \ ] - l $
然后注意，你能使某个位置被放进队列里的条件是此数大于 \(mid\) , 且在枚举 \(i\) 的时候 放入 $ i - mid $
此处的依据：
如果你早在枚举 $ i - mid $ 时就将其放入队列 ， 那么在当他被 \(( i - mid , i )\) 区间内某个数判断时，有可能被 $push_ front() \ or \ push_ back() $ 掉。
那就寄了。所以这么维护。
细节看码吧。
关于我在单队中插入元素时加了一个 \(n\) (其实加不加无所谓的)
因为 $ dp[ \ l \ ] - l $ 这个东西是可能负的，我给强转正。但没什么用。
· \(Code\)
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std ;
const int N = 5e5 + 4 ;
int n , s ;
int w[ N ] ;
int dp[ N ] ;
int maxn = 0 , minn = 1e7 ;
namespace IO {
.........//qcin && qcout
} using namespace IO;
struct Deque
{
int q[ N ] ;
int head = 1 , tail = 0 ;
void clear( )
{
memset( q , 0 , sizeof( q ) ) ;
head = 1 ; tail = 0 ;
}
int front( )
{
return q[ head ] ;
}
int back( )
{
return q[ tail ] ;
}
void push_back( int pri )
{
q[ ++ tail ] = pri ;
}
void pop_front( )
{
head ++ ;
}
void pop_back( )
{
tail -- ;
}
bool empty( )
{
return head > tail ;
}
} q ;
bool check( int mid )
{
q.clear( ) ;
for ( int i = 1 ; i<= n ; ++ i )
{
dp[ i ] = 0 ;
}
int p = 0 ;
for ( int i = 1 ; i <= n ; ++ i )
{
if( i >= mid )
{
int point = i - mid ;
while ( !q.empty( ) && dp[ point ] + n - point > dp[ q.back( ) ] + n - q.back( ) )
{
q.pop_back( ) ;
}
q.push_back( point ) ;
}
dp[ i ] = dp[ i - 1 ] ;
while ( !q.empty( ) && i - q.front( ) > w[ i ] ) q.pop_front( ) ;
if( q.empty( ) ) ;
else dp[ i ] = max( dp[ i ] , dp[ q.front( ) ] + i - q.front( ) ) ;
p = max( p , dp[ i ] ) ;
}
return p >= ( n * s - 1 ) / 100 + 1 ;
}
signed main( )
{
#ifndef ONLINE_JUDGE
freopen ( "1.in" , "r" , stdin ) ;
freopen ( "1.out" , "w" , stdout ) ;
#endif
qcin >> n ;
for ( int i = 1 ; i <= n ; ++ i )
{
qcin >> w[ i ] ;
maxn = max( maxn , w[ i ] ) ;
minn = min( minn , w[ i ] ) ;
}
qcin >> s ;
int left = 1 , right = maxn ;
int ans = 0 ;
while ( left <= right )
{
int mid = ( left + right ) >> 1 ;
if( check( mid ) )
{
left = mid + 1 ;
}
else
{
right = mid - 1 ;
}
}
qcout << right ;
}