斜率优化
斜率优化其实不是很难，可以理解为在平面上的一些点作为决策点，而你现在有一条斜率为 \(k\) 的直线，你需要使其经过一个合适的点，使得这条线的截距最大/最小化。这个显然可以使这些点组成一个上/下凸包、然后二分找到斜率相近的那条线段进行转移。
一个点的两维都不连续的例题：「NOI2007」货币兑换。需要使用 CDQ 分治来做。当然，也可以强行在线使得其只能用 Splay（当然，也可以用二进制分组多一个 \(\Theta(\log)\) 艹过去）
// P4027.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 200;
const double eps = 1e-7;
int n, q[MAX_N], top;
double SA[MAX_N], SB[MAX_N], rate[MAX_N], f[MAX_N];
struct node
{
double x, y;
int id;
} nodes[MAX_N], tmp[MAX_N];
double slope(int i, int j)
{
if (fabs(nodes[i].x - nodes[j].x) < eps)
return 1e-15;
return (nodes[i].y - nodes[j].y) / (nodes[i].x - nodes[j].x);
}
double calc(int i, int j)
{
double VB = f[j] / (rate[j] * SA[j] + SB[j]);
return SA[i] * VB * rate[j] + SB[i] * VB;
}
int binary_search(double k)
{
int l = 1, r = top - 1, res = top;
while (l <= r)
{
int mid = (l + r) >> 1;
if (slope(q[mid], q[mid + 1]) <= k)
res = mid, r = mid - 1;
else
l = mid + 1;
}
return q[res];
}
void solve(int l, int r)
{
if (l == r)
{
f[l] = max(f[l], f[l - 1]), nodes[l].id = l;
nodes[l].y = f[l] / (rate[l] * SA[l] + SB[l]);
nodes[l].x = nodes[l].y * rate[l];
return;
}
int mid = (l + r) >> 1;
solve(l, mid), top = 0;
for (int i = l; i <= mid; i++)
{
while (top > 1 && slope(q[top - 1], q[top]) <= slope(q[top - 1], i))
top--;
q[++top] = i;
}
for (int i = mid + 1; i <= r; i++)
f[i] = max(f[i], calc(i, nodes[binary_search(-SA[i] / SB[i])].id));
solve(mid + 1, r);
int lptr = l, rptr = mid + 1, ptr = l;
while (lptr <= mid && rptr <= r)
if (nodes[lptr].x < nodes[rptr].x || (fabs(nodes[lptr].x - nodes[rptr].x) < 1e-9 && nodes[lptr].y < nodes[rptr].y))
tmp[ptr] = nodes[lptr], lptr++, ptr++;
else
tmp[ptr] = nodes[rptr], rptr++, ptr++;
while (lptr <= mid)
tmp[ptr] = nodes[lptr], lptr++, ptr++;
while (rptr <= r)
tmp[ptr] = nodes[rptr], rptr++, ptr++;
for (int i = l; i <= r; i++)
nodes[i] = tmp[i];
}
int main()
{
scanf("%d%lf", &n, &f[0]);
for (int i = 1; i <= n; i++)
scanf("%lf%lf%lf", &SA[i], &SB[i], &rate[i]), f[i] = f[0];
solve(1, n), printf("%.10lf\n", f[n]);
return 0;
}
决策单调性
一个很经典的例题：LibreOJ #6039. 「雅礼集训 2017 Day5」珠宝。这其中也包含了一个背包 DP 的套路。
首先这个证明很容易，对于每一个固定的价格 \(c\)，转移式如下：
\[ dp[i] = \max_{j \bmod c = i \bmod c, j < i} dp[j] + pre[\frac{i – j}{c}] \]
假设要转移一个 \(j_1 < j_2 < i_1 < i_2\)，显然 \(prefix\) 是一个增量单调递减的数组，如果 \(prefix\) 部分足够长，则 \(dp\) 也会足够小。这样肯定不优。
// LOJ6039.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e6 + 200, MAX_K = 5e4 + 200, MAX_C = 330;
typedef long long ll;
int n, m, pos[MAX_N], ptot;
ll dp[MAX_C][MAX_K];
deque<ll> prefix[MAX_C];
void solve(int cid, int cost, int l, int r, int L, int R)
{
if (l > r || L > R)
return;
int mid = (l + r) >> 1, gpt = -1;
for (int i = L; i <= min(R, mid); i++)
if ((mid - i <= prefix[cost].size() - 1) && (gpt == -1 || dp[cid - 1][pos[gpt]] + prefix[cost][mid - gpt] < dp[cid - 1][pos[i]] + prefix[cost][mid - i]))
gpt = i;
if (l == r)
return (void)(dp[cid][pos[mid]] = dp[cid - 1][pos[gpt]] + prefix[cost][mid - gpt]);
solve(cid, cost, l, mid, L, gpt), solve(cid, cost, mid + 1, r, gpt, R);
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1, c, v; i <= n; i++)
scanf("%d%d", &c, &v), prefix[c].push_back(v);
for (int i = 1; i < MAX_C; i++)
if (!prefix[i].empty())
{
sort(prefix[i].begin(), prefix[i].end()), reverse(prefix[i].begin(), prefix[i].end());
for (int j = 1, siz = prefix[i].size(); j < siz; j++)
prefix[i][j] += prefix[i][j - 1];
prefix[i].push_front(0);
}
int ctot = 0;
for (int i = 1; i < MAX_C; i++)
if (!prefix[i].empty())
{
ctot++;
for (int start_pos = 0; start_pos < i; start_pos++)
{
ptot = 0;
for (int p = start_pos; p <= m; p += i)
pos[++ptot] = p;
solve(ctot, i, 1, ptot, 1, ptot);
}
}
for (int i = 1; i <= m; i++)
printf("%lld ", dp[ctot][i]);
puts("");
return 0;
}
一些套路
无根树
例题：https://kalorona.com/oi/cf-742f/
考虑先做 DP，然后再固定重心。当然需要容斥一下两个重心的情况。
还有一个和树哈希放在一起的题目：https://kalorona.com/oi/bzoj-3162/
根号分治
这个老生常谈了，我记得 LOJ 有个背包题就是这么搞得。UOJ 也有个这样的题。