Description

在一年前贏得了小鎮(zhèn)的最佳草坪比賽后，FJ變得很懶，再也沒(méi)有修剪過(guò)草坪。現(xiàn)在，
新一輪的最佳草坪比賽又開(kāi)始了，FJ希望能夠再次奪冠。

然而，FJ的草坪非常臟亂，因此，FJ只能夠讓他的奶牛來(lái)完成這項(xiàng)工作。FJ有N
(1 <= N <= 100,000)只排成一排的奶牛，編號(hào)為1...N。每只奶牛的效率是不同的，
奶牛i的效率為E_i(0 <= E_i <= 1,000,000,000)。

靠近的奶牛們很熟悉，因此，如果FJ安排超過(guò)K只連續(xù)的奶牛，那么，這些奶牛就會(huì)罷工
去開(kāi)派對(duì):)。因此，現(xiàn)在FJ需要你的幫助，計(jì)算FJ可以得到的最大效率，并且該方案中
沒(méi)有連續(xù)的超過(guò)K只奶牛。

Input

* 第一行：空格隔開(kāi)的兩個(gè)整數(shù)N和K

* 第二到N+1行：第i+1行有一個(gè)整數(shù)E_i

Output

* 第一行：一個(gè)值，表示FJ可以得到的最大的效率值。?

題解： ?

定義 $f_{i}$ 表示不選 $i$ 的最優(yōu)價(jià)值.
則有 $f_{i}=max(f_{j}-sum_{j})+sum_{i-1}$
用單調(diào)隊(duì)列維護(hù)一下 $max(f_{j}-sum_{j})$ 即可.
注意一下 $j$ 的合法范圍，適當(dāng)時(shí)候彈掉. ? #include<iostream> #include<cstdio> #include<cstring> #include<algorithm>#define setIO(s) freopen(s".in","r",stdin) #define N 100010 #define ll long longusing namespace std;ll n, k, maxn, ans, head = 1, tail = 1; ll c[N], sum[N], dp[N], q[N], a[N];ll max(ll a,ll b ) {return a > b ? a : b; }int main() {// setIO("input"); scanf( "%lld%lld", &n, &k );for(ll i = 1; i <= n; i++ ) {scanf( "%lld", &c[i] );sum[i] = sum[i - 1] + c[i];}ll ans=0; for(ll i = 1; i <= n + 1; i++ ) {while( head <= tail && q[head] < i - k - 1 ) head++; dp[i] = dp[q[head]] - sum[q[head]] + sum[i - 1];ans=max(ans,dp[i]); while( head <= tail && dp[q[tail]] - sum[q[tail]] <= dp[i] - sum[i] ) tail--;q[++tail] = i;}printf( "%lld\n", ans);return 0; }

　　

轉(zhuǎn)載于:https://www.cnblogs.com/guangheli/p/11062520.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ 2442: [Usaco2011 Open]修剪草坪 单调队列的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。