决策单调性之 单调队列优化¶
例题 #1 Pictures with Kittens (hard version)¶
给你一个数列\(a\)，你需要选择\(m\)个元素，使得连续的\(k\)个元素都至少有一个被选中。
需要你最大化选出来的所有数的和。
要求\(O(n^2)\)算法
我们首先写出\(O(n^3)\)的代码
定义\(f_{i,j}\)为考虑前i个物品，选j个的最大和，且强制选i。
然后我们就发现\(f_{i,j}\)的注意区间可以使用单调队列维护。每次要转移前，在队列前部弹出已经不在K范围内的。转移后，先弹出队列后部没有当前值优的值，然后再将当前值推入。
#include<bits/stdc++.h>
using namespace std;
#define rd read()
#define int long long
inline int read(){
int x;
cin>>x;
return x;
}
#define cdbg(x) cerr<<#x<<" : "<<x<<endl;
/*
策略：
间隔不得超过K-1
选择x个的最大价值
f_i,j 考虑前i个，选择了j个且第i个必选的最大价值
*/
const int INF=1e9;
const int N=5e3+5;
int f[N][N];
int a[N];
list<int> ls[N];
signed main(){
int n=rd,K=rd;
int x=rd;
for(int i=1;i<=n;i++){
a[i]=rd;
}
if(n/K>x){
puts("-1");
exit(0);
}
memset(f,-0x3f3f,sizeof f);
f[0][0]=0;
ls[0].push_back(0);
for(int i=1;i<=n;i++){
// for(int j=max(0,i-K);j<i;j++){
for(int k=i;k;k--){
while(ls[k-1].size()&&ls[k-1].front()<i-K)ls[k-1].pop_front();
// cerr<<i<<k<<j<<k-1<<endl;
if(ls[k-1].size()) f[i][k]=max(f[i][k],f[ls[k-1].front()][k-1]+a[i]);
while(ls[k].size()&&f[ls[k].back()][k]<=f[i][k])ls[k].pop_back();
ls[k].push_back(i);
}
// }
}
int ans=-INF;
for(int i=0;i<K;i++){
ans=max(ans,f[n-i][x]);
}
cout<<ans<<endl;
return 0;
}
例题 #2 [USACO10NOV] Buying Feed G¶
题目描述
约翰开车来到镇上，他要带\(K\)吨饲料回家。运送饲料是需要花钱的，如果他的车上有\(X\)吨饲料，每公里就要花费\(X^2\)元，开车D公里就需要\(D\times X^2\)元。约翰可以从\(N\)家商店购买饲料，所有商店都在一个坐标轴上，第\(i\)家店的位置是\(X_i\)，饲料的售价为每吨\(C_i\)元，库存为\(F_i\)。
约翰从坐标\(X=0\)开始沿坐标轴正方向前进，他家在坐标\(X=E\)上。为了带\(K\)吨饲料回家，约翰最少的花费是多少呢？假设所有商店的库存之和不会少于\(K\)。
举个例子，假设有三家商店，情况如下所示：
| 坐标 | \(X=1\) | \(X=3\) | \(X=4\) | \(E=5\) |
|---|---|---|---|---|
| 库存 | \(1\) | \(1\) | \(1\) | |
| 售价 | \(1\) | \(2\) | \(2\) |
如果\(K=2\)，约翰的最优选择是在离家较近的两家商店购买饲料，则花在路上的钱是\(1+4=5\)，花在商店的钱是\(2+2=4\)，共需要\(9\)元。
输入格式
第\(1\)行:三个整数\(K,E,N\) 第\(2..N+1\)行:第\(i+1\)行的三个整数代表,\(X_i,F_i,C_i\).
输出格式
一个整数,代表最小花费
\(1 \leq K \leq 10000 , 1 \leq E \leq 500 , 1 \leq N \leq 500\)
\(0 < Xi < E, 1 \leq Fi \leq 10000, 1 \leq C_i \leq 10^7\)
思路¶
理解不难。
Luogu P4544 [USACO10NOV]Buying Feed G - 燃烧的冰块_husky 的博客 - 洛谷博客
std
/*
CB Ntsc
*/
#include <algorithm>
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define pf first
#define ps second
#define err cerr<<"Error"
#define rd read()
// #define nl putc('\n')
#define ot write
#define nl putchar('\n')
inline int rd
{
int xx=0,ff=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9') xx=xx*10+(ch-'0'),ch=getchar();
return xx*ff;
}
inline void write(int out)
{
if(out<0) putchar('-'),out=-out;
if(out>9) write(out/10);
putchar(out%10+'0');
}
const int INF = 1e13;
const int S=1e6+5;
const int maxlog = 10;
const int N = 510;
const int M = 10010;
template <class T>
inline T min(T a, T b) {
return a < b ? a : b;
}
struct node {
int x;
int w;
int v;
node(): x(0), w(0), v(0){}
node(int x_, int w_, int v_): x(x_), w(w_), v(v_) {}
inline bool operator < (node &a) {
return this->x < a.x;
}
};
node s[N];
int W, n, d[N][M];
int que[M];
inline int calc(int i, int k) {
return d[i - 1][k] + (s[i].x - s[i - 1].x) * k * k - s[i].v * k;
}
signed main() {
int E;
W=rd,E=rd,n=rd;
s[0] = node(0, 0, 0);
for (int i = 1, x, w, v; i <= n; ++i) {
x=rd,w=rd,v=rd;
s[i] = node(x, w, v);
}
s[n + 1] = node(E, 0, 0);
sort(s, s + n + 2);
memset(d, 0x3f, sizeof(d));
d[0][0] = 0;
for (int i = 1; i <= n + 1; ++i) {
int l = 1, r = 0;
for (int j = 0; j <= W; ++j) {
while (calc(i, que[r]) > calc(i, j) && l <= r)
--r;
if (j - que[l] > s[i].w && l <= r)
++l;
que[++r] = j;
d[i][j] = calc(i, que[l]) + s[i].v * j;
}
}
printf("%lld", d[n + 1][W]);
}
/*
2 5
0 1 1 1 1
0 1 1 2 4
0 2 1 2 1
0 2 1 1 4
*/
例题 #3 [CSP-S2019] 划分¶
题目描述
2048 年，第三十届 CSP 认证的考场上，作为选手的小明打开了第一题。这个题的样例有 \(n\) 组数据，数据从 \(1 \sim n\) 编号，\(i\) 号数据的规模为 \(a_i\)。
小明对该题设计出了一个暴力程序，对于一组规模为 \(u\) 的数据，该程序的**运行时间**为 \(u^2\)。然而这个程序运行完一组规模为 \(u\) 的数据之后，它将在任何一组规模**小于** \(u\) 的数据上运行错误。样例中的 \(a_i\) 不一定递增，但小明又想在不修改程序的情况下正确运行样例，于是小明决定使用一种非常原始的解决方案：将所有数据划分成若干个数据段，段内数据编号**连续**，接着将同一段内的数据合并成新数据，其规模等于段内原数据的**规模之和**，小明将让新数据的规模能够递增。
也就是说，小明需要找到一些分界点 \(1 \leq k_1 \lt k_2 \lt \cdots \lt k_p \lt n\)，使得
\(\sum_{i=1}^{k_1} a_i \leq \sum_{i=k_1+1}^{k_2} a_i \leq \cdots \leq \sum_{i=k_p+1}^{n} a_i\)
注意 \(p\) 可以为 \(0\) 且此时 \(k_0 = 0\)，也就是小明可以将所有数据合并在一起运行。
小明希望他的程序在正确运行样例情况下，运行时间也能尽量小，也就是**最小化**
\((\sum_{i=1}^{k_1} a_i)^2 + (\sum_{i=k_1+1}^{k_2} a_i)^2 + \cdots + (\sum_{i=k_p+1}^{n} a_i)^2\)
小明觉得这个问题非常有趣，并向你请教：给定 \(n\) 和 \(a_i\)，请你求出最优划分方案下，小明的程序的最小运行时间。
输入格式
由于本题的数据范围较大，部分测试点的 \(a_i\) 将在程序内生成。
第一行两个整数 \(n, type\)。\(n\) 的意义见题目描述，\(type\) 表示输入方式。
-
若 \(type = 0\)，则该测试点的 \(a_i\) 直接给出。输入文件接下来：第二行 \(n\) 个以空格分隔的整数 \(a_i\)，表示每组数据的规模。
-
若 \(type = 1\)，则该测试点的 \(a_i\) 将**特殊生成**，生成方式见后文。输入文件接下来：第二行六个以空格分隔的整数 \(x, y, z, b_1, b_2, m\)。接下来 \(m\) 行中，第 \(i (1 \leq i \leq m)\) 行包含三个以空格分隔的正整数 \(p_i, l_i, r_i\)。
对于 \(type = 1\) 的 23~25 号测试点，\(a_i\) 的生成方式如下：
给定整数 \(x, y, z, b_1, b_2, m\)，以及 \(m\) 个三元组 \((p_i, l_i, r_i)\)。
保证 \(n \geq 2\)。若 \(n \gt 2\)，则 \(\forall 3 \leq i \leq n, b_i = (x \times b_{i−1} + y \times b_{i−2} + z) \mod 2^{30}\)。
保证 \(1 \leq p_i \leq n, p_m = n\)。令 \(p_0 = 0\)，则 \(p_i\) 还满足 \(\forall 0 \leq i \lt m\) 有 \(p_i \lt p_{i+1}\)。
对于所有 \(1 \leq j \leq m\)，若下标值 \(i (1 \leq i \leq n)\)满足 \(p_{j−1} \lt i \leq p_j\)，则有
\(a_i = \left(b_i \mod \left( r_j − l_j + 1 \right) \right) + l_j\)
上述数据生成方式仅是为了减少输入量大小，标准算法不依赖于该生成方式。
输出格式
输出一行一个整数，表示答案。
【数据范围】
| 测试点编号 | \(n \leq\) | \(a_i \leq\) | \(type =\) |
|---|---|---|---|
| \(1 \sim 3\) | \(10\) | \(10\) | 0 |
| \(4 \sim 6\) | \(50\) | \(10^3\) | 0 |
| \(7 \sim 9\) | \(400\) | \(10^4\) | 0 |
| \(10 \sim 16\) | \(5000\) | \(10^5\) | 0 |
| \(17 \sim 22\) | \(5 \times 10^5\) | \(10^6\) | 0 |
| \(23 \sim 25\) | \(4 \times 10^7\) | \(10^9\) | 1 |
对于\(type=0\)的所有测试点,保证最后输出的答案\(\leq 4 \times 10^{18}\)
所有测试点满足：\(type \in \{0,1\}\)，\(2 \leq n \leq 4 \times 10^7\)，\(1 \leq a_i \leq 10^9\)，\(1 \leq m \leq 10^5\)，\(1 \leq l_i \leq r_i \leq 10^9\)，\(0 \leq x,y,z,b_1,b_2 \lt 2^{30}\)。
思路¶
可以证明在条件允许下分得越多时间越小。在划分数目相同的情况下，我们尽可能让每一块平均。预计时间复杂度为\(O(n)\)
\(f(i,j)\)：当前已经划分好了前\(i\)个数，下一次直接划分出\([i+1,j]\)的最小运行时间。
设前缀和\(s_i=\sum_{j=1}^ia_j\)，然后有转移：\(f(i,j)=\min_{(0\le k<i)\land (s_i-s_k\le s_j-s_i)}\{f(k,i)+(s_j-s_i)^2\}\) ~~不难发现，转移的时候，如果\(i\)相同，那么随着\(j\)的增大，\(k\)的取值范围是增大的。所以从小到大枚举\(j\)，然后挪动\(k\)，用一个变量维护\(\min\{f(k,i)\}\)，计算得到答案。
我们不难发现如下的性质： $a2+b2\le(a+b)^2 $这个式子告诉了我们尽量多分段。
既然如此，对于每一个\(i\)，转移的时候，我们实际上只需要找到第一个可行的\(k\)就可以了（有一些\(k\)会导致无法成功分段）。用\(g(i)\)来记录这个第一个\(k\)。
考虑快速求出这个\(g(i)\)。从\(g(i)\)的定义入手： **\(g(i)\)是最大的\(k\)使得\(s_i-s_k\ge s_k-s_{g(k)} (**（即满足递增条件）移项的到： \(s_i\ge 2s_k-s_{g(k)}\) 同时，\)g(i)\)是递增的。所以对于\(i\)，如果\(j<g(i)\)，那么\(j\)不可能成为\(g(i+1)\)，这就是决策的单调性，因此我们从前往后扫一遍即可。
另外，由于\(\forall 1\le i\le n,1\le g(i)< i\)，所以我们可以用一个单调队列来维护可能可以成为答案的\(j\)，然后每次找到单调队列里面最大的且可行的那个作为\(g(i)\)即可。 考虑往单调队列里面插入一个值。设\(v(i)=2s_i-s_{g(i)}\)，则我们应该在插入的时候弹掉队尾的所有\(v\ge v(i)\)的值。假如\(v\)对应的位置可以成为一个\(g\)，那么\(i\)必然可以，而且更优。
代码¶
卡空间
#include<bits/stdc++.h>
#define rep(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define per(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
#define int long long
#define pii pair<int,int>
#define LL __int128
#define lc(x) (x<<1)
#define rc(x) (x<<1|1)
#define rd read()
int read(){
int xx=0,ff=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9') xx=xx*10+(ch-'0'),ch=getchar();
return xx*ff;
}
void write(LL out){
if(out<0) putchar('-'),out=-out;
if(out>9) write(out/10);
putchar(out%10+'0');
}
const int N=2e5+15;
const int INF=1e9+5;
const int MOD = 1<<30;
const int MAXN = 40000005;
const int MAXM = 100005;
signed n,type,q[MAXN],g[MAXN];
int l[MAXM],r[MAXM],p[MAXM];
int s[MAXN],b[MAXN];
int calc(int x) {return 2*s[x]-s[g[x]];}
signed main()
{
n=read();type=read();
if(type==0)
{
// cerr<<"YES";
for(int i=1;i<=n;i++)
s[i]=s[i-1]+read();
}
else
{
int x=read(),y=read(),z=read(),m,now=1;
b[1]=read();b[2]=read();m=read();
for(int i=1;i<=m;i++)
p[i]=read(),l[i]=read(),r[i]=read();
for(int i=3;i<=n;i++)
b[i]=(x*b[i-1]+y*b[i-2]+z)%MOD;
for(int i=1;i<=n;i++)
{
if(i>p[now]) now++;
s[i]=s[i-1]+(b[i]%(r[now]-l[now]+1))+l[now];
}
}
int head=1,tail=1;
for(int i=1;i<=n;i++)
{
while(head<tail && calc(q[head+1])<=s[i]) head++;
g[i]=q[head];
while(head<tail && calc(q[tail])>=calc(i)) tail--;
q[++tail]=i;
}
int now=n;LL ans=0;
while(now) ans+=((LL)s[now]-s[g[now]])*(s[now]-s[g[now]]),now=g[now];
write(ans);
}