CONTENT: DP III
DETAIL: DP杂题
BB
找不到更多曲子了，暂时不放曲子 QAQ
本文的题目堆了挺久了，所以其实蒟蒻也忘得差不多了，会有许多疏漏+bug QAQ
Serval and Rooted Tree - CodeForces 1153D
Description
给定一棵有k个叶子节点的树，每个叶子节点上有一个数字[1, k]，且这些数字不重复使用，每个非叶子节点上有一个属性，要么是max，取其孩子节点中的最大值；要么是min，取其孩子节点中的最小值
现求根节点的最大值
Sample Input
6
1 0 1 1 0 1
1 2 2 2 2
5
1 0 1 0 1
1 1 1 1
8
1 0 0 1 0 1 1 0
1 1 2 2 3 3 3
9
1 1 0 0 1 0 1 0 1
1 1 2 2 3 3 4 4
Sample Output
1
4
4
5
Solution
直接按相对排名算，考虑维护每个节点的最大值，使用树形dp
当为min时，dp(u) = sum{ dp(v) - 1 } + 1，也就是把孩子节点中除维护的最大值，剩下都尽量填满，填满后最小的就是这些值的个数+1
当为max时，枚举孩子节点，把其他孩子节点的值拿去垫底，求出最大值，即dp(u) = max{ sum(u) - sum(v) + dp(v) }
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 15;
struct edge {
int v, nxt;
};
edge e[N << 1];
int head[N], tot;
int type[N];
int dp[N], sum[N];
inline void init() {
memset(head, -1, sizeof(head));
tot = 0;
}
inline void addEdge(int u, int v) {
e[tot] = edge{v, head[u]};
head[u] = tot++;
}
inline void dfs(int u) {
if(head[u] == -1) {
sum[u] = 1;
dp[u] = 1;
return;
}
dp[u] = 1;
sum[u] = 0;
for(int i = head[u]; ~i; i = e[i].nxt) {
int v = e[i].v;
dfs(v);
sum[u] += sum[v];
}
for(int i = head[u]; ~i; i = e[i].nxt) {
int v = e[i].v;
if(type[u]) {
dp[u] = max(dp[u], sum[u] - sum[v] + dp[v]);
} else {
dp[u] += (dp[v] - 1);
}
}
}
int main() {
int n;
while(~scanf("%d", &n)) {
init();
for(int i = 1; i <= n; i++) {
scanf("%d", &type[i]);
}
for(int u = 2; u <= n; u++) {
int v;
scanf("%d", &v);
addEdge(v, u);
}
dfs(1);
printf("%d\n", dp[1]);
}
}
Summary
具体值未知时，可考虑使用相对排名进行DP
The Fair Nut and the Best Path - CodeForces 1083A
Description
给定一棵树，每一个节点有一个值wi，每条边的长度为ci，经过每一个点可以累加该值wi，经过每一条边会消耗该值ci，现求一条路径使得该值恒为正且该值最终最大
Sample Input
3
1 3 3
1 2 2
1 3 2
5
6 3 2 5 0
1 2 10
2 3 3
2 4 1
1 5 1
Sample Output
3
7
Solution
一眼就可以看出这是求 最大连续子数组，难点在于怎么样保证中途值恒为正
蒟蒻认为这依赖于一个结论，即最大连续子数组中的最大值所在段从任意端点开始累加都是不会出现负数的
然后就可以做了 QAQ
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 15;
struct edge {
int v, nxt;
ll w;
};
edge e[N << 1];
int head[N], tot;
int val[N];
ll dp[N];
inline void init() {
memset(head, -1, sizeof(head));
tot = 0;
}
inline void addEdge(int u, int v, ll w) {
e[tot] = edge{v, head[u], w};
head[u] = tot++;
}
inline void dfs(int u, int pre, ll& ans) {
dp[u] = val[u];
ans = max(ans, dp[u]);
for(int i = head[u]; ~i; i = e[i].nxt) {
int v = e[i].v;
if(v == pre) {
continue;
}
dfs(v, u, ans);
ans = max(ans, dp[u] + dp[v] - e[i].w);
dp[u] = max(dp[u], dp[v] + val[u] - e[i].w);
}
}
int main() {
int n;
while(~scanf("%d", &n)) {
init();
for(int i = 1; i <= n; i++) {
scanf("%d", &val[i]);
}
for(int i = 1; i <= n - 1; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
addEdge(u, v, w);
addEdge(v, u, w);
}
ll ans = 0;
dfs(1, -1, ans);
printf("%lld\n", ans);
}
}
Summary
- 最大连续子序列和中，若下标从i到j的子序列和如果是最大的，那么下标从i到j和下标从j到i中一定不会在累加过程中出现负数！可以证明；
- 若连续子序列和为sum，沿某一方向求得连续子序列和出现负数，那么sum不是这一序列中的最大值
Rescue - UVALive 5012
Description
（懒得翻译 = =）
The princess is trapped in a magic place. In this place, there are N magic stones. In order to rescue the princess, you should destroy all the stones. The N stones are in a straight line. We number them as s1, s2, . . . , sn from left to right. Each stone has a magic strength m1, m2, . . . , mn. You have a powerful skill that can do some damage to the stones. To release the skill, you should stand to the right of some stone (si). Then you throw a power ball towards left. Initially, this ball has a power of p. When it hits a stone, it will do some damage to the stone and its power will be decreased, and the ball will continue to fly left to the next stone if its power is still positive. Formally, if you stand to the right of si and the power ball’s initial power is p, then the ball will do max(0, p − (i − j) ∗ (i − j)) damage to sj , for each j ≤ i. So from this formula, we can see that the damage to stone sj is only determined by the initial power of the ball and the number of stones between si and sj .
A stone is destroyed if the accumulated damage you do is larger than its magic strength. Note that even if a stone is destroyed, it will not disappear; your magic ball will do damage to it and the power will be decreased by that stone. You are not strong enough so that you can release at most k magic balls. It will cost a lot of energy if the power of the magic ball is too high. So what is the minimum value of p with which you can destroy all the magic stones, with no more than k magic balls? You can choose where to release each magic ball as your will, and the power of the ball must be a positive integer.
Sample Input
2
1 1
1
3 1
1 4 5
Sample Output
2
6
Solution
首先需要猜结论，那就是应该从右边向左边发射且选择最靠右的位置，这样最优。为什么呢？贪心证明太难 QAQ 蒟蒻当时是假设了一下如果在此基础上向右滑动一个单位，会发现有些覆盖不到，有些又有剩余
剩下就是二分伤害值，然后使用差分思想动态维护一波和与平方和，这样每次二分后的计算就是线性的
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e4 + 15;
ll a[N], tag[N];
bool solve(int n, int k, ll p) {
ll ret = 0;
ll sumsqr = 0, sum = 0, cnt = 0;
int klen = sqrt(p);
for(int i = n; i >= 1; i--) {
if(a[i] >= cnt * p - sumsqr) {
ll delta = (a[i] - (cnt * p - sumsqr)) / p + 1;
ret += delta;
cnt += delta;
tag[max(i - klen, 0)] += delta;
}
if(tag[i]) {
cnt -= tag[i];
sumsqr -= tag[i] * klen * klen;
sum -= tag[i] * klen;
tag[i] = 0;
}
sumsqr += 2 * sum + cnt;
sum += cnt;
}
return ret <= k;
}
int main() {
int t;
scanf("%d", &t);
while(t--) {
ll n, k;
scanf("%lld%lld", &n, &k);
for(int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
}
ll l = 1, r = (ll)1e18, ans = r;
while(l <= r) {
ll mid = (l + r) >> 1;
if(solve(n, k, mid)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
printf("%lld\n", ans);
}
}
Strip - CodeForces 488D
Description
给定一个序列，现将他们分割成若干个连续子序列，使得每个子序列至少有l个元素，且极差不超过s
问子序列的最少数量
Sample Input
7 2 2
1 3 1 2 4 1 2
7 2 2
1 100 1 100 1 100 1
Sample Output
3
-1
Solution
显然dp(i)=min { dp(j)+1 }，但是N太大了，想方法优化，显然dp(i)是非递减的，记录pre为dp(i-1)的分割点，那么对于dp(i)，pre只可能向前不可能向后，因为如果向后(pre–)，能成立的情况下，dp(i-1)也会选择那个分割点，能取得最优情况，如果不成立，那么dp(i)也不成立，因为仍然包含最大值最小值相差超过阈值的情况。因此，用尺取法搞搞
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e6 + 15;
const int K = 20;
const int inf = 0x3f3f3f3f;
int a[N], dp[N];
pii rmq[N][K];
inline void build(int n) {
for(int j = 1; j < K; j++) {
for(int i = 1; i + (1 << j) - 1 <= n; i++) {
rmq[i][j].first = max(rmq[i][j - 1].first, rmq[i + (1 << (j - 1))][j - 1].first);
rmq[i][j].second = min(rmq[i][j - 1].second, rmq[i + (1 << (j - 1))][j - 1].second);
}
}
}
inline int query(int l, int r) {
int j = (int)log2(r - l + 1);
int maxx = max(rmq[l][j].first, rmq[r - (1 << j) + 1][j].first);
int minn = min(rmq[l][j].second, rmq[r - (1 << j) + 1][j].second);
return maxx - minn;
}
int main() {
int n, s, l;
while(~scanf("%d%d%d", &n, &s, &l)) {
memset(dp, 0x3f, sizeof(dp));
dp[0] = 0;
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
rmq[i][0].first = rmq[i][0].second = a[i];
}
build(n);
int pre = 0;
for(int i = 1; i <= n; i++) {
while(pre < i - l && (query(pre + 1, i) > s || dp[pre] >= inf)) {
pre++;
}
dp[i] = (pre <= i - l && query(pre + 1, i) <= s ? dp[pre] + 1 : inf);
}
printf("%d\n", dp[n] >= inf ? -1 : dp[n]);
}
}
Summary
- 在包含最大值、最小值的问题中，可以尝试考虑最大值最小值的位置
- 优化DP时，可以考虑DP的单调性
Shovels Shop - CodeForces 1154F
Description
（懒得翻译）
There are n shovels in the nearby shop. The i-th shovel costs ai bourles.
Misha has to buy exactly k shovels. Each shovel can be bought no more than once.
Misha can buy shovels by several purchases. During one purchase he can choose any subset of remaining (non-bought) shovels and buy this subset.
There are also m special offers in the shop. The j-th of them is given as a pair (xj,yj), and it means that if Misha buys exactly xj shovels during one purchase then yj most cheapest of them are for free (i.e. he will not pay for yj most cheapest shovels during the current purchase).
Misha can use any offer any (possibly, zero) number of times, but he cannot use more than one offer during one purchase (but he can buy shovels without using any offers).
Your task is to calculate the minimum cost of buying k shovels, if Misha buys them optimally.
Sample Input
7 4 5
2 5 4 2 6 3 1
2 1
6 5
2 1
3 1
9 4 8
6 8 5 1 8 1 1 2 1
9 2
8 4
5 3
9 7
5 1 4
2 5 7 4 6
5 4
Sample Output
7
17
17
Solution
一个显然的DP状态是dp(i)=min{dp(i-x[j]) + sum(i - (x[i] - y[i]) + 1, ..., i)}，时间复杂度O(MK)，高达4e8（然而队友说可以过emmmm），如果能够直接在dp上枚举分割点，那么只需要O(K^2)，定义dp(i)为选i个物品的最小代价，那么如果在dp上枚举分割点，则dp(i) = min{dp(i), dp(j) + sum(j + g(i-j) : i) }，其中g(i)为购买i件物品时可以免去费用的物品数最大值，可以发现，这样dp后，把offer和dp分离了开来（原先是既要枚举offer又要dp），只需要预处理一下g(i)数组，就可以做到O(K^2)的DP
#include <bits/stdc++.h>
using namespace std;
const int N = (int)2e5 + 5;
typedef long long ll;
int dp[N], sum[N];
int maxFreeNums[N];
int main(){
int n, m, k;
while(~scanf("%d%d%d", &n, &m, &k)) {
memset(maxFreeNums, 0, sizeof(maxFreeNums));
for(int i = 1; i <= n; i++) {
scanf("%d", &sum[i]);
}
while(m--) {
int x, y;
scanf("%d%d", &x, &y);
maxFreeNums[x] = max(maxFreeNums[x], y);
}
for(int i = 2; i <= n; i++) {
maxFreeNums[i] = max(maxFreeNums[i - 1], maxFreeNums[i]);
}
sort(sum + 1, sum + n + 1);
for(int i = 1; i <= k; i++) {
sum[i] += sum[i - 1];
dp[i] = sum[i];
}
for(int i = 1; i <= k; i++) {
for(int j = 0; j < i; j++) {
dp[i] = min(dp[i], dp[j] + sum[i] - sum[j + maxFreeNums[i - j]]);
}
}
printf("%d\n", dp[k]);
}
}
Summary
- 是否在DP时，可以只在范围较小的数组上通过枚举端点DP，而不是跨越两个数组DP？
Pearls - HDU 1300
Description
（懒得翻译）
In Pearlania everybody is fond of pearls. One company, called The Royal Pearl, produces a lot of jewelry with pearls in it. The Royal Pearl has its name because it delivers to the royal family of Pearlania. But it also produces bracelets and necklaces for ordinary people. Of course the quality of the pearls for these people is much lower then the quality of pearls for the royal family. In Pearlania pearls are separated into 100 different quality classes. A quality class is identified by the price for one single pearl in that quality class. This price is unique for that quality class and the price is always higher then the price for a pearl in a lower quality class.
Every month the stock manager of The Royal Pearl prepares a list with the number of pearls needed in each quality class. The pearls are bought on the local pearl market. Each quality class has its own price per pearl, but for every complete deal in a certain quality class one has to pay an extra amount of money equal to ten pearls in that class. This is to prevent tourists from buying just one pearl.
Also The Royal Pearl is suffering from the slow-down of the global economy. Therefore the company needs to be more efficient. The CFO (chief financial officer) has discovered that he can sometimes save money by buying pearls in a higher quality class than is actually needed. No customer will blame The Royal Pearl for putting better pearls in the bracelets, as long as the prices remain the same.
For example 5 pearls are needed in the 10 Euro category and 100 pearls are needed in the 20 Euro category. That will normally cost: (5+10)*10 + (100+10)*20 = 2350 Euro.
Buying all 105 pearls in the 20 Euro category only costs: (5+100+10)*20 = 2300 Euro.
The problem is that it requires a lot of computing work before the CFO knows how many pearls can best be bought in a higher quality class. You are asked to help The Royal Pearl with a computer program.
Given a list with the number of pearls and the price per pearl in different quality classes, give the lowest possible price needed to buy everything on the list. Pearls can be bought in the requested, or in a higher quality class, but not in a lower one.
Sample Input
2
2
100 1
100 2
3
1 10
1 11
100 12
Sample Output
330
1344
Solution
本题在经过贪心WA了之后，忽然想到可以DP
可以DP是因为传递性，如果一个物品把它转成了价值为p1的物品，再转成价值为p2的物品，和直接转成价值p2的物品是没差的
所以可以枚举一下转成的物品，这样就相当于把原来的物品分割成k段求最小值，k也要枚举，那就是经典的dp方程dp(i, k) = min { dp(j, k - 1) + (sum{a[j + 1], ..., a[i]} + 10) * p[i] }
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100 + 15;
const int SIZE = 26;
int a[N], p[N];
ll dp[N][N];
int main() {
int t;
scanf("%d", &t);
while(t--) {
memset(dp, 0x3f, sizeof(dp));
int n;
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d%d", &a[i], &p[i]);
a[i] += a[i - 1];
dp[i][1] = (ll)(a[i] + 10) * p[i];
}
for(int k = 2; k <= n; k++) {
for(int i = k; i <= n; i++) {
for(int j = k - 1; j < i; j++) {
dp[i][k] = min(dp[i][k], dp[j][k - 1] + (a[i] - a[j] + 10) * p[i]);
}
}
}
ll ans = 0x3f3f3f3f3f3f3f3fLL;
for(int k = 1; k <= n; k++) {
ans = min(ans, dp[n][k]);
}
printf("%lld\n", ans);
}
}
