「做题记录」动态规划选做 — Part 1
stripe_python · · 算法·理论
Part 1 主要是线性结构上的最优化 DP 问题,会涉及一些 DP 优化。Part 2。
HDU5501 The Highest Mark
给出
n 个任务(a_i,b_i,c_i) 和一个时刻上限m 。你可以在任意时刻开始完成一个任务,完成任务需要花费c_i 的时间。若在t 时刻完成且t \le m ,则获得a_i-t\times b_i 的得分。不允许同时进行多个任务,可以以任意顺序完成任务。最大化得分并输出。
多测,
T \le 10 ,n \le 1000 ,m \le 3000 ,1 秒,128 MB。
:::::success[题解] 邻项交换确定 DP 顺序模板题。
如果我们可以确定一个做题顺序,就可以顺着做 01 背包。设
考虑做 exchange argument 来确定 DP 顺序。设当前用时为
- 先
i 后j 的得分为X=a_i-(t+c_i)b_i+a_j-(t+c_i+c_j)b_j ; - 先
j 后i 的得分为Y=a_j-(t+c_j)b_j+a_i-(t+c_i+c_j)b_i 。
作差得
所以定义
| 复杂度 |
|---|
:::::info[代码]
const int N = 3005;
int n, m;
struct node {
int a, b, c;
} a[N];
i64 f[N];
void _main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i].a >> a[i].b >> a[i].c;
sort(a + 1, a + n + 1, [](const node& x, const node& y) {
return 1LL * x.c * y.b < 1LL * y.c * x.b;
});
fill(f, f + m + 1, 0);
for (int i = 1; i <= n; i++)
for (int j = m; j >= a[i].c; j--)
f[j] = max(f[j], f[j - a[i].c] + a[i].a - 1LL * j * a[i].b);
cout << *max_element(f, f + m + 1) << '\n';
}
:::::
P10971 Cookies
现有
m 个元素要分给n 个人,第i 个人有属性值a_i ,如果有x 个人拿到的元素比第i 个人多,则产生a_i\times x 的代价。每个人至少要分到一个元素,且所有m 个元素要全部分完,求最小代价,并构造一组方案。
:::::success[题解]
观察性质起手:对于
按照
讨论给第
- 分配的元素数目
>1 :等效于分配j-i 个元素给前i 个人,每人少一个元素不影响代价的计算,即f_{i,j} \gets f_{i,j-i} ; - 分配的元素数目
=1 :枚举前k 个人分配1 个元素,则f_{i,j} \gets f_{k,j-(i-k)}+k\times \sum\limits_{l=k+1}^i a_l 。
| 对 |
|---|
:::::info[代码]
const int N = 5005;
using node = pair<int, int>;
int n, m, f[31][N], pre[N], tmp[N], ans[N];
node a[N], opt[31][N];
void dfs(int i, int j) {
if (i == 0 && j == 0) return;
auto [ni, nj] = opt[i][j];
dfs(ni, nj);
if (i == ni) {
for (int k = 1; k <= ni; k++) tmp[k]++;
} else {
for (int k = ni + 1; k <= n; k++) tmp[k] = 1;
}
}
void _main() {
cin >> n >> m;
for (int i = 1, x; i <= n; i++) cin >> x, a[i] = {x, i};
sort(a + 1, a + n + 1, greater<node>());
for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + a[i].first;
memset(f, 0x3f, sizeof(f)), f[0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = i; j <= m; j++) {
if (f[i][j - i] < f[i][j]) {
f[i][j] = f[i][j - i];
opt[i][j] = {i, j - i};
}
for (int k = 0; k < i; k++) {
int v = f[k][j - i + k] + k * (pre[i] - pre[k]);
if (v < f[i][j]) f[i][j] = v, opt[i][j] = {k, j - i + k};
}
}
}
cout << f[n][m] << '\n';
dfs(n, m);
for (int i = 1; i <= n; i++) ans[a[i].second] = tmp[i];
for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
}
:::::
P8903 [USACO22DEC] Bribing Friends G
现有
n 个元素(p_i,c_i,x_i) 。你初始持有a 元钱和b 张优惠券。对于第i 个元素,你可以支付c_i 元获得p_i 的得分。同时,如果你支付x_i 张优惠劵,你还可以获得1 元的折扣,折扣的上限为c_i 。最大化得分并输出。
:::::success[题解]
容易设计一个 DP:记
我们需要发现性质,然后用贪心优化 DP。
考虑如下情景:我们已经确定了最优解中选择哪些元素。这种情况下有一个贪心:我们按
对于前面的元素,我们一定是尽量使用优惠券直到买满。那么整个场面上至多有一个元素没有被买满,是使用钱 + 优惠券混用得到的。
拓展到一般情况,将元素按
我们可以对前缀做一个
| 复杂度 |
|---|
:::::info[代码]
const int N = 2005;
int n, a, b, f[N][N], g[N][N];
struct node {
int p, c, x;
} c[N];
void _main() {
cin >> n >> a >> b;
for (int i = 1; i <= n; i++) cin >> c[i].p >> c[i].c >> c[i].x;
sort(c + 1, c + n + 1, [](const node& a, const node& b) -> bool {
return a.x < b.x;
});
for (int i = 1; i <= n; i++) {
int w = c[i].c * c[i].x;
for (int j = 0; j <= b; j++) {
f[i][j] = f[i - 1][j];
if (j >= w) f[i][j] = max(f[i][j], f[i - 1][j - w] + c[i].p);
}
}
for (int i = n; i >= 1; i--) {
for (int j = 0; j <= a; j++) {
g[i][j] = g[i + 1][j];
if (j >= c[i].c) g[i][j] = max(g[i][j], g[i + 1][j - c[i].c] + c[i].p);
}
}
int res = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= c[i].c; j++) {
if (j * c[i].x > b || c[i].c - j > a) continue;
res = max(res, f[i - 1][b - j * c[i].x] + g[i + 1][a - c[i].c + j] + c[i].p);
}
} cout << res;
}
:::::
【无题解】P11233 [CSP-S 2024] 染色
【无题解】P9119 [春季测试 2023] 圣诞树
P8162 [JOI 2022 Final] 让我们赢得选举 / Let's Win the Election
给出
n 个任务(a_i,b_i) ,b_i 可能为+\infty 。你初始持有d=1 ,对于第i 个任务,可以选择一个实数x ,若dx \ge a_i 则获得1 的得分,若dx \ge b_i 则令d \gets d+1 。此操作支付x 的代价。每个任务只能获得一次得分,求获得
k 得分的最小代价。
:::::success[题解]
对第
如果我们钦定了
如果我们确定了
根据上述分析,按
进一步,我们可以使用调整法说明:在这段特定前缀不存在
于是我们有
:::::
:::::info[代码]
const int N = 505;
const double inf = 1e18;
int n, k;
struct node {
double a, b;
} a[N];
double v[N], f[N][N];
double work(int m) {
for (int i = 1; i <= n; i++) v[i] = a[i].a;
for (int i = 1; i <= n; i++) fill(f[i], f[i] + i + 1, inf);
f[0][0] = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= min(m, i); j++) {
chkmin(f[i + 1][j], f[i][j] + a[i + 1].a / (m + 1));
chkmin(f[i + 1][j + 1], f[i][j] + a[i + 1].b / (j + 1));
}
}
double res = inf;
for (int i = k; i <= n; i++) chkmin(res, f[i][m]);
for (int i = k - 1; i >= m; i--) {
sort(v + i + 1, v + n + 1);
chkmin(res, f[i][m] + accumulate(v + i + 1, v + k + 1, 0.0) / (m + 1));
} return res;
}
void _main() {
cin >> n >> k;
for (int i = 1, x, y; i <= n; i++) {
cin >> x >> y;
a[i].a = x, a[i].b = (y == -1 ? inf : y);
}
sort(a + 1, a + n + 1, [](const node& a, const node& b) -> bool {
return a.b < b.b;
});
double res = inf;
for (int i = 0; i <= k; i++) res = min(res, work(i));
cout << fixed << setprecision(12) << res;
}
:::::
P11630 [WC2025] 士兵
给出
n 个二元组(a_i,b_i) ,一次操作支付m 的代价,将一个区间上的所有a_i 减1 。所有操作结束后,你的得分为\sum\limits_{i=1}^n b_i[a_i \le 0] 。最大化得分减去代价的值。
多测,
\sum n \le 5 \times 10^5 ,1 \le a_i,m \le 10^9 ,-10^9 \le b_i \le 10^9 。2 秒,1024 MB。
:::::success[题解]
我们任意赋一组非负整数
写出答案式子为
容易把贡献拆到每个位置
进一步,考察操作的性质。注意到令
- 当
b_i>0 时,有决策x_i \gets a_i ,获得b_i 的得分。 - 当
b_i<0 时,有决策x_i \gets a_i-1 ,避免-b_i 的代价。
此时我们并不需要记录
枚举上一个突变点
倒序枚举
int n, m, a[N], b[N], c[N], f[N];
void _main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i] >> b[i], c[i] = a[i] - (b[i] < 0);
fill(f + 1, f + n + 1, -1e18);
for (int i = 1; i <= n; i++) {
int v = 0;
for (int j = i - 1; j >= 0; j--) {
f[i] = max(f[i], max(0LL, b[i]) + f[j] - m * max(0LL, c[i] - c[j]) + v);
if (c[i] >= a[j]) v += b[j];
}
}
cout << *max_element(f, f + n + 1) << '\n';
}
令
- 若
c_j \ge c_i ,此时无消除代价,我们需要查询c_j \in [c_i,+\infty) 的最大得分f_j+h(j,i) 。 - 若
c_j < c_i ,此时支付m(c_i-c_j) 的代价,我们需要查询c_j \in [0,c_i] 的最大得分f_j+m\times c_j+h(j,i) 。
| 离散化以后,将两棵线段树建在 |
|---|
:::::info[代码]
int n, m, len, a[N], b[N], c[N], d[N << 1];
int idx(int x) {return lower_bound(d + 1, d + len + 1, x) - d;}
struct segtree {
#define ls (rt << 1)
#define rs (rt << 1 | 1)
constexpr static int inf = 1e18;
int val[N << 3], add[N << 3], cmax[N << 3];
void pushup(int rt) {val[rt] = max(val[ls], val[rs]);}
void apply(int rt, int ad, int cm) {
val[rt] = max(val[rt] + ad, cm), add[rt] += ad;
cmax[rt] = max(cmax[rt] + ad, cm);
}
void pushdown(int rt) {
apply(ls, add[rt], cmax[rt]), apply(rs, add[rt], cmax[rt]), add[rt] = 0, cmax[rt] = -inf;
}
void build(int l = 0, int r = len, int rt = 1) {
add[rt] = 0, cmax[rt] = -inf, val[rt] = -inf;
if (l == r) return;
int mid = (l + r) >> 1;
build(l, mid, ls), build(mid + 1, r, rs);
}
void uadd(int tl, int tr, int c, int l = 0, int r = len, int rt = 1) {
if (tl <= l && r <= tr) return apply(rt, c, -inf), void();
int mid = (l + r) >> 1;
pushdown(rt);
if (tl <= mid) uadd(tl, tr, c, l, mid, ls);
if (tr > mid) uadd(tl, tr, c, mid + 1, r, rs);
pushup(rt);
}
void umax(int tl, int tr, int c, int l = 0, int r = len, int rt = 1) {
if (tl <= l && r <= tr) return apply(rt, 0, c), void();
int mid = (l + r) >> 1;
pushdown(rt);
if (tl <= mid) umax(tl, tr, c, l, mid, ls);
if (tr > mid) umax(tl, tr, c, mid + 1, r, rs);
pushup(rt);
}
int ask(int x, int l = 0, int r = len, int rt = 1) {
if (l == r) return val[rt];
int mid = (l + r) >> 1;
pushdown(rt);
return x <= mid ? ask(x, l, mid, ls) : ask(x, mid + 1, r, rs);
}
} T1, T2;
void _main() {
cin >> n >> m, len = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i] >> b[i], c[i] = a[i] - (b[i] < 0);
d[++len] = a[i], d[++len] = a[i] - 1;
}
sort(d + 1, d + len + 1), len = unique(d + 1, d + len + 1) - d - 1;
T1.build(), T2.build();
T1.umax(0, 0, 0), T2.umax(0, len, 0);
for (int i = 1; i <= n; i++) {
int v1 = T1.ask(idx(c[i])), v2 = T2.ask(idx(c[i])) - m * c[i];
int v = max(v1, v2) + max(0LL, b[i]);
T1.uadd(idx(a[i]), len, b[i]), T2.uadd(idx(a[i]), len, b[i]);
T1.umax(0, idx(c[i]), v), T2.umax(idx(c[i]), len, v + m * c[i]);
} cout << T1.val[1] << '\n';
}
:::::
ABC225F String Cards
给出
n 个字符串S_i 。你需要选出k 个字符串,并按某个顺序拼接,最小化这个串的字典序并输出。
:::::success[题解]
注意到 P1012 即本题
直接选择一段长为
考虑 DP。记
这个 DP 还是错的,仍然没有考虑长度变化带来的问题。如
重设状态为:
视作
:::::info[代码]
const int N = 55;
int n, k;
string s[N], f[N][N];
void _main() {
cin >> n >> k;
string inf(k, 'z' + 1);
for (int i = 1; i <= n; i++) cin >> s[i];
sort(s + 1, s + n + 1, [](const string& a, const string& b) -> bool {
return a + b < b + a;
});
fill(f[n] + 1, f[n] + k + 1, inf), f[n][1] = s[n];
for (int i = n - 1; i >= 1; i--) {
for (int j = 1; j <= k; j++) f[i][j] = min(f[i + 1][j], s[i] + f[i + 1][j - 1]);
}
cout << f[1][k];
}
:::::
:::::success[另解] 其实正序 DP 是可以救活的。
考虑钦定长度,记
此时转移不会受到长度影响:
直接做的复杂度为