其实单调队列就是一种队列内的元素有单调性(单调递增或者单调递减)的队列,答案(也就是最优解)就存在队首,而队尾则是最后进队的元素。因为其单调性所以经常会被用来维护区间最值或者降低DP的维数已达到降维来减少空间及时间的目的。
单调队列的一般应用:
维护区间最值
优化DP
F[i]=min(F[j]+a[i]:j<i)
定义:队列元素保持单调递增(减),而保持的方式就是通过插队,把队尾破坏了单调性的数全部挤掉,从而使队列元素保持单调 。 那么单调队列有什么用呢?优化DP。许多单调队列优化的DP可以使复杂度直接降维,下面就以最简单的一道题为例: Description 烽火台又称烽燧,是重要的军事防御设施,一般建在险要或交通要道上。一旦有敌情发生,白天燃烧柴草,通过浓烟表达信息;夜晚燃烧干柴,以火光传递军情(晓荣的历史课讲过吼),在某两座城市之间有 n 个烽火台,每个烽火台发出信号都有一定代价。为了使情报准确地传递,在连续 m 个烽火台中至少要有一个发出信号。请计算总共最少花费多少代价,才能使敌军来袭之时,情报能在这两座城市之间准确传递。 Input 第一行:两个整数 N,M。其中N表示烽火台的个数, M 表示在连续 m 个烽火台中至少要有一个发出信号。接下来 N 行,每行一个数 Wi,表示第i个烽火台发出信号所需代价。 Output 一行,表示答案。 Sample Input 5 3 1 2 5 6 2 Sample Output 4 Data Constraint 对于50%的数据,M≤N≤1,000 。 对于100%的数据,M≤N≤100,000,Wi≤100。 分析题目,由于题目要求连续m个烽火台中至少要有一个发出信号,很容易得出DP转移方程: **F[i]=min(F[j]:i−m<j<i)+a[i]F[i]=min(F[j]:i−m<j<i)+a[i] ** 最直接的方法是枚举状态,对于每一个i,我们在i-m+1到i-1中寻找一个最小的F[j]进行状态转移,枚举状态的时间复杂度是O(n),寻找最小值的状态时间复杂度是O(n),因此这种方法的复杂度是O(n^2)。题目的是数据范围是n<=100000,显然超时。 那么怎么用单调队列优化呢? e.g.状态枚举到i,当m=4时,我们要做的就是在i-3到i-1中找到最小的F[j],那么枚举到i+1时,我们要做的就是要在i-2到i中找到最小的F[j]。 要寻找最小值的区间向后移动了一位,也就是F[i-m+1]的值被抛弃,F[i-1]的值被加入。 这里就可以用单调队列处理了,F[i-1]是插队的数据,F[i-1]有资格插队是因为它更优且更靠近i (又年轻又比你优秀),比它更差的数将被它取代,保留那些数据没有任何好处。而那些已经不再维护区间之外的就不必再对其进行维护,出队即可。看了代码会更加明白:
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; int read() { int x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int n,m,ans=2147483647,head=1,tail=0; int q[100010],a[100010],f[100010]; int main() { n=read(),m=read(); rep(i,1,n)a[i]=read(); rep(i,1,n) { while(head<=tail && f[i-1]<=f[q[tail]])tail--; //注意<=要取等(虽然我们一样优, 但是我比你年轻啊!) q[++tail]=i-1; //当F[i-1]比队尾值更优时把队 尾值弹出,并插入 while(head<=tail && q[head]<i-m)head++;//不属于区间维护内的数弹出 f[i]=f[q[head]]+a[i]; } for(int i=n;i>n-m;i--) ans=min(ans,f[i]); printf("%d",ans); return 0; }
JZOJ 1772 假期 Description 经过几个月辛勤的工作,FJ决定让奶牛放假。假期可以在1…N天内任意选择一段(需要连续),每一天都有一个享受指数W。但是奶牛的要求非常苛刻,假期不能短于P天,否则奶牛不能得到足够的休息;假期也不能超过Q天,否则奶牛会玩的腻烦。FJ想知道奶牛们能获得的最大享受指数。 Input 第一行:N,P,Q. 第二行:N个数字,中间用一个空格隔开,每个数都在longint范围内。 Output 一个整数,奶牛们能获得的最大享受指数。 Sample Input 5 2 4 -9 -4 -3 8 -6 Sample Output 5 Data Constraint 50% 1≤N≤10000 100% 1≤N≤100000 1<=p<=q<=n Hint 选择第3-4天,享受指数为-3+8=5。
思路: 看到区间的问题首先肯定是想到求前缀和, 我们把[1,k]的 和记为sum[k],可以得到sum[i] = sum[i - 1] + a[i], [l,r]的和即为sum[r] - sum[l - 1](这里视sum[0] = 0)。(减法原理) 我们假设选择的区间为[l,r]且r固定,可知 r−B+1≤l≤r−A+1若要使[l,r]区间的值最大,则sum[l - 1] 需最小,才可使得sum[r] - sum[l - 1]最小。 当i右移一位到i+1,因为p,q为给定不变的值,对应寻 找最小sum[l-1]的区间也右移一位
#include<bits/stdc++.h> #define ll long long #define N 1000010 #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; int read() { int x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } ll sum[N],q[N]; ll n,ans=-2147483647,A,B; int main() { //freopen("input.txt","r",stdin); n=read(),A=read(),B=read(); rep(i,1,n) sum[i]=sum[i-1]+read(); int head=0,tail=1; rep(i,A,n) { while(head<=tail && q[head]<i-B)//不处于维护范围内的,出队 head++; while(head<=tail && sum[i-A]<=sum[q[tail]])//更优的sum[l - 1]予以插队 tail--; q[++tail]=i-A; ans=max(ans,sum[i]-sum[q[head]]);//更新答案 } printf("%lld\n",ans); return 0; }
在一年前赢得了小镇的最佳草坪比赛后,FJ 变得很懒,再也没有修剪过草坪。 现在,新一轮的最佳草坪比赛又开始了,FJ 希望能够再次夺冠。 然而,FJ 的草坪非常脏乱,因此,FJ 只能够让他的奶牛来完成这项工作。 FJ 有 N 只排成一排的奶牛,编号为 1 到 N。 每只奶牛的效率是不同的,奶牛 i 的效率为 Ei。 编号相邻的奶牛们很熟悉,如果 FJ 安排超过 K 只编号连续的奶牛,那么这些奶牛就会罢工去开派对。 因此,现在 FJ 需要你的帮助,找到最合理的安排方案并计算 FJ 可以得到的最大效率。 注意,方案需满足不能包含超过 K 只编号连续的奶牛。 输入格式 第一行:空格隔开的两个整数 N 和 K; 第二到 N+1 行:第 i+1 行有一个整数 Ei。 输出格式 共一行,包含一个数值,表示 FJ 可以得到的最大的效率值。 数据范围 1≤N≤105, 0≤Ei≤109 输入样例: 5 2 1 2 3 4 5 输出样例: 12 样例解释 FJ 有 5 只奶牛,效率分别为 1、2、3、4、5。 FJ 希望选取的奶牛效率总和最大,但是他不能选取超过 2 只连续的奶牛。 因此可以选择第三只以外的其他奶牛,总的效率为 1 + 2 + 4 + 5 = 12。 #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; const int N = 1e5 + 10; int n, m; LL s[N]; LL f[N]; int q[N]; LL g(int i) { if (!i) return 0; return f[i - 1] - s[i]; } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i ++ ) { scanf("%lld", &s[i]); s[i] += s[i - 1]; } int hh = 0, tt = 0; for (int i = 1; i <= n; i ++ ) { if (q[hh] < i - m) hh ++ ; f[i] = max(f[i - 1], g(q[hh]) + s[i]); while (hh <= tt && g(q[tt]) <= g(i)) tt -- ; q[ ++ tt] = i; } printf("%lld\n", f[n]); return 0; }
John 打算驾驶一辆汽车周游一个环形公路。 公路上总共有 n 个车站,每站都有若干升汽油(有的站可能油量为零),每升油可以让汽车行驶一千米。 John 必须从某个车站出发,一直按顺时针(或逆时针)方向走遍所有的车站,并回到起点。 在一开始的时候,汽车内油量为零,John 每到一个车站就把该站所有的油都带上(起点站亦是如此),行驶过程中不能出现没有油的情况。 任务:判断以每个车站为起点能否按条件成功周游一周。 输入格式 第一行是一个整数 n,表示环形公路上的车站数; 接下来 n 行,每行两个整数 pi,di,分别表示表示第 i 号车站的存油量和第 i 号车站到 顺时针方向 下一站的距离。 输出格式 输出共 n 行,如果从第 i 号车站出发,一直按顺时针(或逆时针)方向行驶,能够成功周游一圈,则在第 i 行输出 TAK,否则输出 NIE。 数据范围 3≤n≤106, 0≤pi≤2×109, 0≤di≤2×109 输入样例: 5 3 1 1 2 5 2 0 1 5 4 输出样例: TAK NIE TAK NIE TAK #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; const int N = 2e6 + 10; int n; int oil[N], dist[N]; LL s[N]; int q[N]; bool ans[N]; int main() { scanf("%d", &n); for (int i = 1; i <= n; i ++ ) { scanf("%d%d", &oil[i], &dist[i]); s[i] = s[i + n] = oil[i] - dist[i]; } for (int i = 1; i <= n * 2; i ++ ) s[i] += s[i - 1]; int hh = 0, tt = 0; q[0] = n * 2 + 1; for (int i = n * 2; i >= 0; i -- ) { if (q[hh] > i + n) hh ++ ; if (i < n) { if (s[i] <= s[q[hh]]) ans[i + 1] = true; } while (hh <= tt && s[q[tt]] >= s[i]) tt -- ; q[ ++ tt] = i; } dist[0] = dist[n]; for (int i = 1; i <= n; i ++ ) s[i] = s[i + n] = oil[i] - dist[i - 1]; for (int i = 1; i <= n * 2; i ++ ) s[i] += s[i - 1]; hh = 0, tt = 0; q[0] = 0; for (int i = 1; i <= n * 2; i ++ ) { if (q[hh] < i - n) hh ++ ; if (i > n) { if (s[i] >= s[q[hh]]) ans[i - n] = true; } while (hh <= tt && s[q[tt]] <= s[i]) tt -- ; q[ ++ tt] = i; } for (int i = 1; i <= n; i ++ ) if (ans[i]) puts("TAK"); else puts("NIE"); return 0; }
高二数学《绿色通道》总共有 n 道题目要抄,编号 1,2,…,n,抄第 i 题要花 ai 分钟。 小 Y 决定只用不超过 t 分钟抄这个,因此必然有空着的题。 每道题要么不写,要么抄完,不能写一半。 下标连续的一些空题称为一个空题段,它的长度就是所包含的题目数。 这样应付自然会引起马老师的愤怒,最长的空题段越长,马老师越生气。 现在,小 Y 想知道他在这 t 分钟内写哪些题,才能够尽量减轻马老师的怒火。 由于小 Y 很聪明,你只要告诉他最长的空题段至少有多长就可以了,不需输出方案。 输入格式 第一行为两个整数 n,t。 第二行为 n 个整数,依次为 a1,a2,…,an。 输出格式 输出一个整数,表示最长的空题段至少有多长。 数据范围 0<n≤5×104, 0<ai≤3000, 0<t≤108 输入样例: 17 11 6 4 5 2 5 3 4 5 2 3 4 5 2 3 6 3 5 输出样例: 3 #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 50010, INF = 1e9; int n, m; int w[N]; int f[N], q[N]; bool check(int k) { f[0] = 0; int hh = 0, tt = 0; for (int i = 1; i <= n; i ++ ) { if (hh <= tt && q[hh] < i - k - 1) hh ++ ; f[i] = f[q[hh]] + w[i]; while (hh <= tt && f[q[tt]] >= f[i]) tt -- ; q[ ++ tt] = i; } int res = INF; for (int i = n - k; i <= n; i ++ ) res = min(res, f[i]); return res <= m; } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]); int l = 0, r = n; while (l < r) { int mid = l + r >> 1; if (check(mid)) r = mid; else l = mid + 1; } printf("%d\n", r); return 0; }
有一个 a×b 的整数组成的矩阵,现请你从中找出一个 n×n 的正方形区域,使得该区域所有数中的最大值和最小值的差最小。 输入格式 第一行为三个整数,分别表示 a,b,n 的值; 第二行至第 a+1 行每行为 b 个非负整数,表示矩阵中相应位置上的数。 输出格式 输出仅一个整数,为 a×b 矩阵中所有“n×n 正方形区域中的最大整数和最小整数的差值”的最小值。 数据范围 2≤a,b≤1000, n≤a,n≤b,n≤100, 矩阵中的所有数都不超过 109。 输入样例: 5 4 2 1 2 5 6 0 17 16 0 16 17 2 1 2 10 2 1 1 2 2 2 输出样例: 1 #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 1010, INF = 1e9; int n, m, k; int w[N][N]; int row_min[N][N], row_max[N][N]; int q[N]; void get_min(int a[], int b[], int tot) { int hh = 0, tt = -1; for (int i = 1; i <= tot; i ++ ) { if (hh <= tt && q[hh] <= i - k) hh ++ ; while (hh <= tt && a[q[tt]] >= a[i]) tt -- ; q[ ++ tt] = i; b[i] = a[q[hh]]; } } void get_max(int a[], int b[], int tot) { int hh = 0, tt = -1; for (int i = 1; i <= tot; i ++ ) { if (hh <= tt && q[hh] <= i - k) hh ++ ; while (hh <= tt && a[q[tt]] <= a[i]) tt -- ; q[ ++ tt] = i; b[i] = a[q[hh]]; } } int main() { scanf("%d%d%d", &n, &m, &k); for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m; j ++ ) scanf("%d", &w[i][j]); for (int i = 1; i <= n; i ++ ) { get_min(w[i], row_min[i], m); get_max(w[i], row_max[i], m); } int res = INF; int a[N], b[N], c[N]; for (int i = k; i <= m; i ++ ) { for (int j = 1; j <= n; j ++ ) a[j] = row_min[j][i]; get_min(a, b, n); for (int j = 1; j <= n; j ++ ) a[j] = row_max[j][i]; get_max(a, c, n); for (int j = k; j <= n; j ++ ) res = min(res, c[j] - b[j]); } printf("%d\n", res); return 0; }
所谓1D/1D动态规划,指的是状态数为O(n),每一个状态决策量为O(n)的动态规划方程,直接求解的时间复杂度是O(n2)。但是,绝大多数的方程通过合理的组织与优化都是可以直接优化到O(nlogn)乃至O(n)的时间复杂度的。
优化方法包括:
单调队列优化至O(n)
斜率优化至O(nlogn)或O(n)
决策单调性优化至O(nlogn)
斜率优化Dp问题入门会较为困难,因为这大概是在学习过程中OI选手第一次遇到与数学内容结合的算法。
但斜率优化反而是一个重要的知识点,它简单地将1D/1D动态规划优化至O(n),同时斜率优化也有更困难的延申与拓展。
其中最简单的斜率优化形式还是单调队列,但优化原理大不相同。
对于一个决策j进行考虑,即将考虑的转移是: f(i)=a[i]×x(j)+b[i]×y(j)。 我们使用线性规划进行转化(线性规划大概会在高二学习), 我们以x(j)为横轴,y(j)为纵轴建立平面直角坐标系,这样决 策j就可以用坐标系上的一个点表示。 原方程可以转化为f(i)=min{a[i]×x+b[i]×y},这类似一个 直线的一般式方程,我们将其转化为斜截式方程:y=−abx+f(i)b,假设b>0,则目标是最小化直线的纵截距。 我们用一个斜率为−ab的直线从负无穷向上平移,所碰到的第 一个点即为最优决策j,利用这个点我们可以计算出最优的 f(i)。
不难发现,所有可能的最优决策点必定在平面点集的凸包上,换句话说不在凸包上的点一定不是最优决策点。
当b>0时,我们需要维护一个右下凸包或左上凸包(根据点集的特征决定)。
那么现在我们的任务转化为了维护凸包。
根据直线斜率和数据点分布的特征,我们可以分为三种情况。
这种情况的处理非常简单,因为斜率变化是单调的,因此决策点必然在凸壳上单调移动,我们只需要维护一个单调队列和一个决策指针即可。
对于每一个状态f(i),计算过程如下:
决策指针(队首)后移,直到最佳决策点j。
进行决策并计算f(i)。
计算x(i),y(i),将二元组加入队尾,同时更新凸壳(如图)。
时间复杂度O(n)
我们使用同样的方式维护凸壳,在查询最优决策点的时候,使用二分查找找到最接近的斜率。
时间复杂度为O(nlogn)
虽然决策点仍然在凸壳上,但是在维护凸壳时就有大麻烦了。我们需要一一验证凸性,接着需要拼接凸壳,最坏的时间复杂度O(n),这相当于根本没有优化!
该怎么做呢?分为两种情况:
允许离线:此时我们可以使用cdq分治(上我的博客里的提高算法目录中自己翻)来较为简单地解决这个问题,时间复杂度为O(nlogn)。
强制在线:此时我们只能使用平衡树来维护凸包了,我们以横坐标为关键字建立平衡树,查找和插入的过程均为O(nlogn),在维护凸壳时,先将新数据点Splay到根结点,剩下的结点必定分居左子树与右子树。然后我们以左子树为例,后序遍历依次查找结点,直到找到一个满足凸性的结点,将这个结点Splay到根结点的左儿子,然后我们删掉这个结点的右子树即可,时间复杂度为O(nlogn),但实现起来非常复杂。
有 N 个任务排成一个序列在一台机器上等待执行,它们的顺序不得改变。 机器会把这 N 个任务分成若干批,每一批包含连续的若干个任务。 从时刻 0 开始,任务被分批加工,执行第 i 个任务所需的时间是 Ti。 另外,在每批任务开始前,机器需要 S 的启动时间,故执行一批任务所需的时间是启动时间 S 加上每个任务所需时间之和。 一个任务执行后,将在机器中稍作等待,直至该批任务全部执行完毕。 也就是说,同一批任务将在同一时刻完成。 每个任务的费用是它的完成时刻乘以一个费用系数 Ci。 请为机器规划一个分组方案,使得总费用最小。 输入格式 第一行包含整数 N。 第二行包含整数 S。 接下来 N 行每行有一对整数,分别为 Ti 和 Ci,表示第 i 个任务单独完成所需的时间 Ti 及其费用系数 Ci。 输出格式 输出一个整数,表示最小总费用。 数据范围 1≤N≤5000, 0≤S≤50, 1≤Ti,Ci≤100 输入样例: 5 1 1 3 3 2 4 3 2 3 1 4 输出样例: 153 #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; const int N = 5010; int n, s; int sc[N], st[N]; LL f[N]; int main() { scanf("%d%d", &n, &s); for (int i = 1; i <= n; i ++ ) { scanf("%d%d", &st[i], &sc[i]); st[i] += st[i - 1]; sc[i] += sc[i - 1]; } memset(f, 0x3f, sizeof f); f[0] = 0; for (int i = 1; i <= n; i ++ ) for (int j = 0; j < i; j ++ ) f[i] = min(f[i], f[j] + (sc[i] - sc[j]) * (LL)st[i] + (LL)s * (sc[n] - sc[j])); printf("%lld\n", f[n]); return 0; } 有 N 个任务排成一个序列在一台机器上等待执行,它们的顺序不得改变。 机器会把这 N 个任务分成若干批,每一批包含连续的若干个任务。 从时刻 0 开始,任务被分批加工,执行第 i 个任务所需的时间是 Ti。 另外,在每批任务开始前,机器需要 S 的启动时间,故执行一批任务所需的时间是启动时间 S 加上每个任务所需时间之和。 一个任务执行后,将在机器中稍作等待,直至该批任务全部执行完毕。 也就是说,同一批任务将在同一时刻完成。 每个任务的费用是它的完成时刻乘以一个费用系数 Ci。 请为机器规划一个分组方案,使得总费用最小。 输入格式 第一行包含整数 N。 第二行包含整数 S。 接下来 N 行每行有一对整数,分别为 Ti 和 Ci,表示第 i 个任务单独完成所需的时间 Ti 及其费用系数 Ci。 输出格式 输出一个整数,表示最小总费用。 数据范围 1≤N≤3×105, 1≤Ti,Ci≤512, 0≤S≤512 输入样例: 5 1 1 3 3 2 4 3 2 3 1 4 输出样例: 153 #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; const int N = 300010; int n, s; LL c[N], t[N]; LL f[N]; int q[N]; int main() { scanf("%d%d", &n, &s); for (int i = 1; i <= n; i ++ ) { scanf("%lld%lld", &t[i], &c[i]); t[i] += t[i - 1]; c[i] += c[i - 1]; } int hh = 0, tt = 0; q[0] = 0; for (int i = 1; i <= n; i ++ ) { while (hh < tt && (f[q[hh + 1]] - f[q[hh]]) <= (t[i] + s) * (c[q[hh + 1]] - c[q[hh]])) hh ++ ; int j = q[hh]; f[i] = f[j] - (t[i] + s) * c[j] + t[i] * c[i] + s * c[n]; while (hh < tt && (__int128)(f[q[tt]] - f[q[tt - 1]]) * (c[i] - c[q[tt - 1]]) >= (__int128)(f[i] - f[q[tt - 1]]) * (c[q[tt]] - c[q[tt - 1]])) tt -- ; q[ ++ tt] = i; } printf("%lld\n", f[n]); return 0; } 有 N 个任务排成一个序列在一台机器上等待执行,它们的顺序不得改变。 机器会把这 N 个任务分成若干批,每一批包含连续的若干个任务。 从时刻 0 开始,任务被分批加工,执行第 i 个任务所需的时间是 Ti。 另外,在每批任务开始前,机器需要 S 的启动时间,故执行一批任务所需的时间是启动时间 S 加上每个任务所需时间之和。 一个任务执行后,将在机器中稍作等待,直至该批任务全部执行完毕。 也就是说,同一批任务将在同一时刻完成。 每个任务的费用是它的完成时刻乘以一个费用系数 Ci。 请为机器规划一个分组方案,使得总费用最小。 输入格式 第一行包含两个整数 N 和 S。 接下来 N 行每行有一对整数,分别为 Ti 和 Ci,表示第 i 个任务单独完成所需的时间 Ti 及其费用系数 Ci。 输出格式 输出一个整数,表示最小总费用。 数据范围 1≤N≤3×105, 0≤S,Ci≤512, −512≤Ti≤512 输入样例: 5 1 1 3 3 2 4 3 2 3 1 4 输出样例: 153 #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; const int N = 300010; int n, s; LL t[N], c[N]; LL f[N]; int q[N]; int main() { scanf("%d%d", &n, &s); for (int i = 1; i <= n; i ++ ) { scanf("%lld%lld", &t[i], &c[i]); t[i] += t[i - 1]; c[i] += c[i - 1]; } int hh = 0, tt = 0; q[0] = 0; for (int i = 1; i <= n; i ++ ) { int l = hh, r = tt; while (l < r) { int mid = l + r >> 1; if (f[q[mid + 1]] - f[q[mid]] > (t[i] + s) * (c[q[mid + 1]] - c[q[mid]])) r = mid; else l = mid + 1; } int j = q[r]; f[i] = f[j] - (t[i] + s) * c[j] + t[i] * c[i] + s * c[n]; while (hh < tt && (double)(f[q[tt]] - f[q[tt - 1]]) * (c[i] - c[q[tt - 1]]) >= (double)(f[i] - f[q[tt - 1]]) * (c[q[tt]] - c[q[tt - 1]])) tt -- ; q[ ++ tt] = i; } printf("%lld\n", f[n]); return 0; } 小 S 是农场主,他养了 M 只猫,雇了 P 位饲养员。 农场中有一条笔直的路,路边有 N 座山,从 1 到 N 编号。 第 i 座山与第 i−1 座山之间的距离为 Di。 饲养员都住在 1 号山。 有一天,猫出去玩。 第 i 只猫去 Hi 号山玩,玩到时刻 Ti 停止,然后在原地等饲养员来接。 饲养员们必须回收所有的猫。 每个饲养员沿着路从 1 号山走到 N 号山,把各座山上已经在等待的猫全部接走。 饲养员在路上行走需要时间,速度为 1 米/单位时间。 饲养员在每座山上接猫的时间可以忽略,可以携带的猫的数量为无穷大。 例如有两座相距为 1 的山,一只猫在 2 号山玩,玩到时刻 3 开始等待。 如果饲养员从 1 号山在时刻 2 或 3 出发,那么他可以接到猫,猫的等待时间为 0 或 1。 而如果他于时刻 1 出发,那么他将于时刻 2 经过 2 号山,不能接到当时仍在玩的猫。 你的任务是规划每个饲养员从 1 号山出发的时间,使得所有猫等待时间的总和尽量小。 饲养员出发的时间可以为负。 输入格式 第一行包含三个整数 N,M,P。 第二行包含 n−1 个整数,D2,D3,…,DN。 接下来 M 行,每行包含两个整数 Hi 和 Ti。 输出格式 输出一个整数,表示所有猫等待时间的总和的最小值。 数据范围 2≤N≤105, 1≤M≤105, 1≤P≤100, 1≤Di<1000, 1≤Hi≤N, 0≤Ti≤109 输入样例: 4 6 2 1 3 5 1 0 2 1 4 9 1 10 2 10 3 12 输出样例: 3 #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; const int N = 100010, M = 100010, P = 110; int n, m, p; LL d[N], t[N], a[N], s[N]; LL f[P][M]; int q[M]; LL get_y(int k, int j) { return f[j - 1][k] + s[k]; } int main() { scanf("%d%d%d", &n, &m, &p); for (int i = 2; i <= n; i ++ ) { scanf("%lld", &d[i]); d[i] += d[i - 1]; } for (int i = 1; i <= m; i ++ ) { int h; scanf("%d%lld", &h, &t[i]); a[i] = t[i] - d[h]; } sort(a + 1, a + m + 1); for (int i = 1; i <= m; i ++ ) s[i] = s[i - 1] + a[i]; memset(f, 0x3f, sizeof f); for (int i = 0; i <= p; i ++ ) f[i][0] = 0; for (int j = 1; j <= p; j ++ ) { int hh = 0, tt = 0; q[0] = 0; for (int i = 1; i <= m; i ++ ) { while (hh < tt && (get_y(q[hh + 1], j) - get_y(q[hh], j)) <= a[i] * (q[hh + 1] - q[hh])) hh ++ ; int k = q[hh]; f[j][i] = f[j - 1][k] - a[i] * k + s[k] + a[i] * i - s[i]; while (hh < tt && (get_y(q[tt], j) - get_y(q[tt - 1], j)) * (i - q[tt]) >= (get_y(i, j) - get_y(q[tt], j)) * (q[tt] - q[tt - 1])) tt -- ; q[ ++ tt] = i; } } printf("%lld\n", f[p][m]); return 0; }
决策单调性可以理解为四边形不等式优化Dp的1D/1D版本。
可以利用决策单调性优化的动态规划的特点是:其决策的下标单调。
特征方程:$f(x)=$$\min_{i=1}^{x-1}${$f(i)+w[i,x]}$
已知结论
如果用k(x)表示状态x取到最优值的决策,则决策单调性表述为:
$∀i≤j,k(i)≤k(j)$当且仅当:
$∀i≤j$,w[i,j]+w[i−1,j−1]≤w[i−1,j]+w[i,j−1]
因此满足转移代价四边形不等式,则可以利用决策单调性进行优化。
但是转移的代价是否满足四边形不等式,并非一个很容易判断的问题,因此推荐的姿势是:
在确认动态规划需要优化且不满足以上两种方式时,打表验证决策点是否单调。
记G(x,i)
为状态x根据转移方程f(x)
使用i决策转移的结果。
设决策点i<j
,决策j比i更优(假设问题要求最小化),则G(x,i)≥G(x,j)
将不等式解出后我们可以得到决策j比i更优的条件。
若条件仅有单向限制(另一端为无穷)且不等号不会变向(单调性),则满足决策单调性。
若无解,则满足决策单调性。(决策j无用)
若条件是一段区间(双边限制),则不满足决策单调性。
优化过程:
如何实现决策单调性呢?我们可以在枚举决策的时候,不从1开始,而是从k(x−1)
开始,但这样只能减少常数,并不能降低时间复杂度。
另一种想法时从k(x−1)
开始枚举决策更新f(x)
,一旦发现决策j比决策j+1
更优,就停止决策过程,选择决策j作为f(x)
的最优决策。但这样是错误的,因为决策单调性并没有保证f(j)+w[j,x]
有什么好的性质。
如果我们换一个角度,思考对于一个已经计算出的状态f(j)
,它能够更新哪些状态?这样,每一步过程中的某些决策可能不是最优的,但是当算法结束时所有状态的决策一定是最优的。
一开始,只有f(1)
的函数值被计算出,所以所有状态的当前最优决策点都是1。
决策表:1111111111111111111111111111111111111111111
现在由于f(2)
的值已经确定了,f(2)
的最优决策只能是1,那么我们使用决策2来更新这个决策表。由于决策单调性,新的决策表只能是下面这种形式:
决策表:1111111111111222222222222222222222222222222
因此我们可以使用二分法来寻找1与2之间的转折点,因为如果在一个点x上,决策2更好,所有比x大的状态都是决策2更好;如果x上决策1更好,则所有比x小的状态都是决策1更好。
当决策表更新完毕后,f(3)
即可确定,现在用3更新所有状态,新的决策表只能有以下两种形式:
决策表:1111111111111222222222222222222233333333333
决策表:1111111111333333333333333333333333333333333
此时我们可以设计出整个算法流程:
使用一个栈维护数据,栈中的每一个元素保存一个决策可更新区间的起始位置与结束位置,这些区间肯定相互连接且依次递增。当插入一个新的决策时,从栈顶往栈底扫描栈,依次考察栈顶决策:
如果新决策i比栈顶的决策top对于top起始位置更优,则弹栈,全部抛弃栈顶决策top,将区间继承给新决策i,继续扫描下一个栈顶决策。
如果栈顶决策top对于其起始位置更优,则转折点必定在top所能更新的区间中,二分查找转折点,然后将新决策i入栈,结束更新操作。
时间复杂度:
由于一个决策只会入栈一次,均摊时间为O(1),但是由于二分查找的存在,时间复杂度为O(nlogn)。