对于形如
\[f_i=\max(f_{L≤j≤R}+w_i) \]的状态转移方程，也就是转移来自之前某个定长区间的最值，我们可以使用单调队列来维护区间最值，从而优化时间复杂度。
烽火传递
我们看到题目可以想到用 \(f_i\) 表示考虑到 \(i\) 这个烽火台，点第 \(i\) 个的合法方案中的最小代价
那么可以想到，点了第 \(i\) 个烽火台，前面 \([i-m,i-1]\) 的区间内至少要点一个，然后我们的状态转移方程就是前面区间最小值加上自己所需的代价
边界 \(f_0=0\)
答案 \(\min(f_{n-m+1 \to n})\)
然后这一道题要求定长区间最小值，我们可以用单调队列优化
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10;
int n, m, w[N], f[N], q[N], ans = N;
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++ )
cin >> w[i];
int hh = 0, tt = 0;
for(int i = 1; i <= n; i ++ )
{
if(q[hh] < i - m) hh ++ ;//队头滑出
f[i] = f[q[hh]] + w[i];
while(hh <= tt && f[q[tt]] >= f[i]) tt -- ;//将比当前元素更差的扔出去
q[++ tt] = i;//添加元素
if(i > n - m) ans = min(ans, f[i]);//更新答案
}
cout << ans << endl;
return 0;
}
修剪草坪
这道题目有两种解法，一种是直接计算(未懂)，另一种是一种转化的思路
题目让我们最多连续选 \(k\) 个使得效率最大，我们可以看成在 \(k+1\) 里不选一个，使得不选的效率最小，然后用总效率减去不选的效率就可以得到答案
\(f_i\) 表示考虑到 \(i\) 这个奶牛，不选第 \(i\) 个的的最小不选代价
然后同样从前 \(k + 1\) 个转移
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
LL w[N], q[N], h, t, n, k;
int main()
{
cin >> n >> k;
LL sum = 0;
for(int i = 1; i <= n; i ++ )
{
cin >> w[i];
sum += w[i];
}
for(int i = 1; i <= n; i ++ )
{
w[i] += w[q[h]];//这里放在前面是因为我们是k+1个不选一个,如果先把队头弹出答案
if(q[h] < i - k) h ++ ;
while(h <= t && w[q[t]] >= w[i]) t -- ;
q[++ t] = i;
}
cout << sum - w[q[h]];
return 0;
}
旅行问题
环形问题我们会想到化环为链 ，那么很容易想到将原数组复制两次，这样原问题就转化成了
在新数组中是否存在长度为 \(n + 1\) 的合法区间
接下来我们考虑顺时针的问题
顺时针
每个点 \(i\) 表示从 \(i\) 点加 \(o_i\) 的油再消耗掉 \(d_i\) 的油所剩的油量，也就是 \(o_i-d_i\)
-
更新前缀和 \(s_i\)
-
从任意一点 \(i\) 出发，顺时针走一圈，我们要保证在过程中油量始终 \(≥0\) ，也就是在 \([i,i+n-1]\) 中，对任意的 \(j(i≤j≤i+n-1)\) ,都要保证 \(s_j-s_{i-1}≥0\)， \(i\) 固定，找 \(s_j\) 的最小值，也就是在区间内找 \(s_j\) 最小值，然后与 \(s_i\) 比较
-
这里我们要进行反向遍历，从 \(n\times2\) 到 \(1\) (顺时针需要求出 后面 一段区间中的最值，只有从后往前做才能在处理到当前数的时候，把后面数的信息存下来），由于计算的时候会用到 \(i\) ，所以这里我们就先更新再求值。
逆时针
每个点 \(i\) 表示从 \(i\) 点加 \(o_i\) 的油再消耗掉 \(d_{i-1}\) 的油所剩的油量，也就是 \(o_i-d_{i-1}\) （因为是向后走）
更新 \(s_i\) 这里注意是用 \(s_i+s_{i+1}\) 后缀和，那么以 \(i\) 起点的后缀和为 \(s_j-s_{i+1}\)
在任意情况下都有 \(s_j-s_{i+1} ≥ 0\)
然后正向遍历维护 \(s_j\) 的最小值
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e6 + 10;
typedef long long LL;
int n;
LL s[N];//前缀和
int o[N], d[N];//油量，距离
int q[N];
bool ans[N];//每个点是否能走到
int main()
{
cin >> n;
for(int i = 1; i <= n; i ++ )
cin >> o[i] >> d[i];
for(int i = 1; i <= n; i ++ )
s[i] = s[i + n] = o[i] - d[i];
for(int i =1; i <= 2 * n; i ++ )
s[i] += s[i - 1];
int h = 1, t = 0;
for(int i = 2 * n; i >= 1; i -- )
{
while(h <= t && s[q[t]] >= s[i]) t -- ;
q[++ t] = i;
if(q[h] > i + n - 1) h ++ ;
if(i <= n && s[q[h]] - s[i - 1] >= 0)
ans[i] = true;
}
d[0] = d[n];
for(int i = n; i; i -- )
s[i] = s[i + n] = o[i] - d[i - 1];
for(int i = 2 * n; i; i -- )
s[i] += s[i + 1];
h = 1, t = 0;
for(int i = 1; i <= 2 * n; i ++ )
{
while(h <= t && s[q[t]] >= s[i]) t -- ;
q[++ t] = i;
if(q[h] < i - n + 1) h ++ ;
if(i > n && s[q[h]] - s[i + 1] >= 0)
ans[i - n] = true;
}
for(int i = 1; i <= n; i ++ )
{
if(ans[i])
puts("TAK");
else
puts("NIE");
}
return 0;
}