单调队列 线段树 树状数组
决策单调性优化
凸优化
四边形不等式优化
矩阵快速幂优化
给定 \(n\) 个一模一样的蛋 从 \(x\) 以上的层扔下去会碎 采取最优策略 问最坏扔多少次知道蛋从第几层扔下去刚好会碎
? \(f_{i, j}\) 表示 \(i\) 个蛋 测 \(j\) 层楼的最少次数
转移考虑从 \(k\) 层扔一个蛋 碎不碎
\(f_{i, j} = \min\{\max\{f_{i - 1, k - 1}, f_{i, j - k}\} + 1\}\)
复杂度 \(O(m^3)\)
蛋的个数大于 \(\log m + 1\) 直接二分
把 \(dp\) 的第一维缩小到 \(\log m\) 的级别
复杂度 \(O(m^2 \log m)\)
具有决策单调性(?)
随着 \(k\) 的增大 后面那一项是单调递减的 前面那一项是单调增大的
当有一个位置 \(k_0\) 满足 \(f_{i - 1, k_0 - 1} > f_{i, j - k_0}\)
...
另一种思路
\(f_{i, j}\) 表示用 \(i\) 个蛋 扔 \(j\) 次 最多可以试出多少层
转移时同样考虑蛋碎不碎
\(f_{i, j} = f_{i - 1, j - 1} + f_{i, j - 1} + 1\)
在 \(f_{n, j}\) 中进行二分查找 找给出的 \(m\) 找到给出的 \(j\) 就是要尝试的次数 其中 \(i\) 是 \(\log m\) 级别 考虑 \(j\) 的范围
...
弃
有 \(T\) 天 第 \(i\) 天买股票话 \(Ap_i\) 元 买股票花 \(Bp_i\) 最多能买 \(As_i\) 股 最多能卖 \(Bs_i\) 股 任何时候股票持有量不超过 \(MaxP\) 且两个交易日至少间隔 \(w\) 天 求 \(T\) 天后的最大收益
\(f_{i, j}\) 表示 第 \(i\) 天 持有 \(j\) 股票时的最大收益
套单调队列优化
/*
Time: 5.5
Worker: Blank_space
Source: P2569 [SCOI2010]股票交易
*/
/*--------------------------------------------*/
#include<cstdio>
#include<cstring>
#define Max(x, y) ((x) > (y) ? (x) : (y))
/*--------------------------------------头文件*/
const int A = 1e4 + 7;
const int B = 1e5 + 7;
const int C = 1e6 + 7;
const int D = 1e7 + 7;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
/*------------------------------------常量定义*/
int n, maxp, W, f[2021][2021], q[A], l, r, ans;
/*------------------------------------变量定义*/
inline int read() {
int x = 0, f = 1; char ch = getchar();
while(ch < ‘0‘ || ch > ‘9‘) {if(ch == ‘-‘) f = -1; ch = getchar();}
while(ch >= ‘0‘ && ch <= ‘9‘) {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
return x * f;
}
/*----------------------------------------快读*/
/*----------------------------------------函数*/
int main() {
n = read(); maxp = read(); W = read(); memset(f, 128, sizeof f);
for(int i = 1; i <= n; i++)
{
int AP = read(), BP = read(), AS = read(), BS = read();
for(int j = 0; j <= AS; j++) f[i][j] = -j * AP;
for(int j = 0; j <= maxp; j++) f[i][j] = Max(f[i][j], f[i - 1][j]);
if(i <= W) continue;
l = 1; r = 0;
for(int j = 0; j <= maxp; j++)
{
while(l <= r && f[i - W - 1][q[r]] + q[r] * AP <= f[i - W - 1][j] + j * AP) r--;
q[++r] = j;
while(l <= r && j - q[l] > AS) l++;
if(l <= r) f[i][j] = Max(f[i][j], f[i - W - 1][q[l]] - (j - q[l]) * AP);
}
l = 1; r = 0;
for(int j = maxp; j >= 0; j--)
{
while(l <= r && f[i - W - 1][q[r]] + q[r] * BP <= f[i - W - 1][j] + j * BP) r--;
q[++r] = j;
while(l <= r && q[l] - j > BS) l++;
if(l <= r) f[i][j] = Max(f[i][j], f[i - W - 1][q[l]] + (q[l] - j) * BP);
}
}
for(int j = 0; j <= maxp; j++) ans = Max(ans, f[n][j]);
printf("%d", ans);
return 0;
}
要求两名玩家排成一排的 \(n\) 个石头上跳跃 每个石头给定高度 只能向右跳 跳过的时候会消失 两个人不能站在同一个石头上 游戏分数为两个玩家战国的石头的总数 任选起点 求最高分数
\(f_{i, j}\) 表示一个人在 \(i\) 另一个人在 \(j\) 的最大分数
复杂度 \(O(n^3)\)
树状数组维护最大值
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++) if(i != j)
{
f[i][j] = Max(f[i][j], bit1.sum(a[i]));
f[i][j] = Max(f[i][j], bit2.sum(a[i]));
bit1.add(a[i], f[i][j]); bit2.add(a[j], f[i][j]);
ans = Max(ans, f[i][j]);
}
将一个长度为 \(n\) 的非负序列划分成若干段 每段数字和不超过 \(m\) 求每段最大值和最小的划分方法 输出最小的和
设 \(M(i, j)\) 表示区间 \([i, j]\) 的元素最大值
\(f_i = \min\{f_j, M(j + 1, i) \}\)
发现 \(f_i\) 单调不减 考虑选取什么位置转移
维护递减的队列 存的是符合要求的某一段的最大值 注意这个问题不是可以通过单调队列优化的 需要通过线段树的区间查询最大值优化 \(dp\)
\(16\) 名选手参加淘汰赛 (\(16 \to 8 \to 4 \to 2 \to 1\) )给定两人之间的比赛 知道哪一位一定赢 胜负关系可能出现环 对于每一位选手 询问是否可以通过设计第一轮匹配使得该选手夺冠
状态数 \(O(n)\) 每个状态的决策量 \(O(n)\) 的 \(DP\) 朴素做法一般为 \(O(n^2)\)
一个机器人从原点出发 按订单顺序将若干个物品送到终点 第 \(i\) 个订单要求将 \(m_i\) 个物品送到 \((x_i, y_i)\) 机器人一次最多持有 \(c\) 个物品 但可以回原点补充 机器人只能沿平行于最标轴方向行走 问送完所有物品并回到原点的最小路程
直观的 \(dp\) 设 \(f_i\) 表示送完前 \(i\) 个订单并返回终点的答案 设 \(d_i\) 表示 \((x_i, y_i)\) 到原点的距离
\(f_i = \min\{f_j + d_i + d_j + dis(j + 1, ..., i) \}\)
条件 \(m_{j + 1} + ... + m_i \leq c\)
如果将 \(dis(a, ... , b)\) 改为 \(s_b - s_{a - 1}\)
\(f_i = d_i + s_i + \min\{f_i + d_{j + 1} - s_j \}\)
套单调队列
/*
Time: 5.5
Worker: Blank_space
Source: UVA1169 Robotruck
*/
/*--------------------------------------------*/
#include<cstdio>
#include<cstring>
#define Abs(x) ((x) < 0 ? -(x) : (x))
#define Max(x, y) ((x) > (y) ? (x) : (y))
#define Min(x, y) ((x) < (y) ? (x) : (y))
#define Swap(x, y) ((x) ^= (y) ^= (x) ^= (y))
/*--------------------------------------头文件*/
const int A = 1e4 + 7;
const int B = 1e5 + 7;
const int C = 1e6 + 7;
const int D = 1e7 + 7;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
/*------------------------------------常量定义*/
int T, n, f[B], q[B], l, r, c, d[B], dis[B], w[B], _x, _y;
/*------------------------------------变量定义*/
inline int read() {
int x = 0, f = 1; char ch = getchar();
while(ch < ‘0‘ || ch > ‘9‘) {if(ch == ‘-‘) f = -1; ch = getchar();}
while(ch >= ‘0‘ && ch <= ‘9‘) {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
return x * f;
}
/*----------------------------------------快读*/
void work() {
memset(f, 63, sizeof f); w[0] = dis[0] = d[0] = _x = _y = 0;
c = read(); n = read(); f[0] = 0; l = r = 1; q[1] = 0;
for(int i = 1; i <= n; i++)
{
int x = read(), y = read(); w[i] = read() + w[i - 1]; d[i] = x + y;
dis[i] = Abs(x - _x) + Abs(y - _y) + dis[i - 1];
_x = x; _y = y;
}
for(int i = 1; i <= n; i++)
{
while(l <= r && w[i] - w[q[l]] > c) l++;
f[i] = f[q[l]] + d[i] + d[q[l] + 1] + dis[i] - dis[q[l] + 1];
while(l <= r && f[q[r]] + d[q[r] + 1] - dis[q[r] + 1] >= f[i] + d[i + 1] - dis[i + 1]) r--;
q[++r] = i;
}
printf("%d\n", f[n]);
if(T) puts("");
}
/*----------------------------------------函数*/
int main() {
T = read(); while(T--) work();
return 0;
}
斜率优化
排序 + 斜率优化
原文：https://www.cnblogs.com/blank-space-/p/14732657.html