隊(duì)爺?shù)?Au Plan
【問(wèn)題描述】
隊(duì)爺為了變得越來(lái)越神，他給自己制定了 n 個(gè)任務(wù)，編號(hào)為 1，
2，…,n。隊(duì)爺在完成這些任務(wù)之前有一個(gè)初始興奮值 m，每個(gè)任務(wù)
都有一個(gè)難度值 hard[i],且對(duì)于任何 i>j，有 hard[i]>hard[j]，隊(duì)爺
完成第 i 個(gè)任務(wù)，興奮值至少會(huì)減少 hard[i]，第 i 任務(wù)完成之后，隊(duì)
爺會(huì)受到鼓舞，興奮值又會(huì)增加 s[i]，每個(gè)任務(wù)只完成一次。隊(duì)爺可
以一次完成所有剩余的難度值不超過(guò)現(xiàn)有興奮度的任務(wù)， 這樣只會(huì)消
耗那個(gè)最大的難度值。現(xiàn)在隊(duì)爺想知道完成這 n 個(gè)任務(wù)之后，他的最
大興奮值為多少。
【輸入文件】
第一行 2 個(gè)整數(shù) n，m，如題意。
第二行 n 個(gè)整數(shù)，第 i 個(gè)為 hard[i]。
第三行 n 個(gè)整數(shù)，第 i 個(gè)為 s[i]。
【輸出文件】
一個(gè)整數(shù)，為完成這 n 個(gè)任務(wù)之后的最大興奮值。Orz CC 杯 NOIP 模擬賽
5
【輸入樣例】
5 5
2 4 5 7 9
4 4 3 6 5
【輸出樣例】
14
【樣例解釋】
第一次完成前 2 個(gè)任務(wù)，興奮值為 9；
第二次完成后 3 個(gè)任務(wù)，興奮值為 14。
【數(shù)據(jù)規(guī)模與約定】
對(duì)于 30%的數(shù)據(jù)，1<=n<=2000
對(duì)于另外 20%的數(shù)據(jù)，所有的 s[i]之和小于 200000；
對(duì)于 100%的數(shù)據(jù)，1<=n<=200000，數(shù)據(jù)保證所有任務(wù)都能完成。

100分算法：對(duì)于i狀態(tài)，考慮j，k兩個(gè)決策，i>k>j且f[j]>hard[i]&&f[k]>hard[i]。若j，k不為前面同一個(gè)決策轉(zhuǎn)移得到，則k的決策層數(shù)顯然會(huì)更大，即額外消耗更多，所以j優(yōu)于k；若j，k為前面同一個(gè)決策l轉(zhuǎn)移得到：
f[j]=f[l]-sum[l]+sum[j]-hard[j],f[k]=f[l]-sum[l]+sum[k]-hard[k],
f[j]-f[k]=sum[j]-sum[k]+hard[k]-hard[j],
f[j]-sum[j]-(f[k]-sum[k])=hard[k]-hard[j],
即f[j]-sum[j]> f[k]-sum[k],所以j決策優(yōu)于k決策，
所以對(duì)于每一個(gè)狀態(tài)i，最小的能夠轉(zhuǎn)移到i的決策總是最優(yōu)的，這樣只需要用單調(diào)隊(duì)列維護(hù)決策即可（其實(shí)一個(gè)指針就OK了），時(shí)間復(fù)雜度為O(n)。

program df;
var i,j,n,m,y,z,k,t:longint;
x:int64;
a,b,c,f,min:array[0..300000] of longint;
s:array[0..300000] of int64;

begin
assign(input,’plan.in’);
reset(input);
assign(output,’plan.out’);
rewrite(output);
readln(n,m);
for i:=1 to n do
read(a[i]);
readln;
for i:=1 to n do
read(b[i]);
for i:=1 to n do
s[i]:=s[i-1]+b[i];
f[0]:=m; k:=1;
while m>a[k] do
begin
min[k]:=0;
inc(k);
end;

for i:=1 to n do
begin
f[i]:=f[min[i]]+s[i]-s[min[i]]-a[i];
while (f[i]>=a[k]) and (k<=n) do
begin
min[k]:=i;
inc(k);
end;
end;
writeln(f[n]);
close(input);
close(output);
end.

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

總結(jié)

以上是生活随笔為你收集整理的队爷的 Au Plan（dp+单调队列）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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