总结
通常应用在需要找最值的时候利用单调队列把时间复杂度从$O(n)$降为$O(1)$
E. Rudolf and k Bridges
地址
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| void solve()
{
int n,m,k,d;
cin>>n>>m>>k>>d;
vector<vector<int>> a(n+1,vector<int>(m+1,0));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
a[i][j]++;
}
}
vector<int> cost(n+1,0);
//单调队列优化DP
for(int i=1;i<=n;i++){
vector<int> dp(m+1);
deque<int> q;
dp[1]=1;
q.push_back(1);
for(int j=2;j<=m;j++){
while(q.size() && q.front()<=j-d-2) q.pop_front();
while(q.size() && dp[q.back()]>=dp[j-1]) q.pop_back();
q.push_back(j-1);
dp[j]=dp[q.front()]+a[i][j];
}
cost[i]=dp[m];
}
ll ans=INF;
for(int i=1;i+k-1<=n;i++){
ll t=0;
for(int j=i;j<=i+k-1;j++){
t+=cost[j];
}
ans=min(ans,t);
}
cout<<ans<<"\n";
}
|
P1725 琪露诺
地址
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| void solve()
{
int n,l,r;
cin>>n>>l>>r;
vector<int> a(n+1);
for(int i=0;i<=n;i++){
cin>>a[i];
}
vector<int> dp(n+1,-INF);
dp[0]=a[0];
deque<int> q;
queue<int> tmp;//还没到指定区间内先暂存一下
tmp.push(0);
for(int i=1;i<=n;i++){
while (!q.empty() && q.front() < i - r) {
q.pop_front();
}
while (!tmp.empty() && tmp.front() <= i - l) {//到了合法区间，释放出来
while (!q.empty() && dp[q.back()] < dp[tmp.front()]) {
q.pop_back();
}
q.push_back(tmp.front());
tmp.pop();
}
if (!q.empty()) {
dp[i] = max(dp[i], dp[q.front()] + a[i]);
}
tmp.push(i);
}
ll ans=-INF;
for(int i=n-r+1;i<=n;i++){
ans=max(ans,dp[i]);
}
cout<<ans;
}
|