宝箱
最大权值划分
宝箱
思路
看了严格鸽的知乎
个人感觉严格鸽说的并不是特别的清晰， 我的理解是， 对于每条红边， 它需要最多三次， 最少两次走。 下面这张图
我们如果从第二个绿点往右走再折返回来， 那么实际上第一条红边我们也应该只走了两次， 但是我们把它算上了三次， 这其实对答案是没有影响的， 因为它比正解是要大的， 我们只需要保证一定枚举到了正解(其实是第一个绿点折返)就可以了
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| #include <iostream>
#include <cstdio>
#include <algorithm>
int n;
struct P
{
long long x;
int tp;
bool operator < (P tmp) const
{
if(x < tmp.x)
return true;
else if(x > tmp.x)
return false;
else
return tp < tmp.tp;
}
} p[200005];
long long f[200005], pre[200005];
long long ans = 1e18;
int main()
{
scanf("%d", &n);
int ed = n * 2;
for(int i = 1; i <= ed; i ++)
scanf("%lld", &p[i].x), p[i].tp = (i <= n);
std:: sort(p + 1, p + ed + 1);
int cntb = 0;
f[1] = 1;
for(int i = 1; i <= ed; i ++)
{
pre[i] = pre[i - 1] + (p[i].x - p[i - 1].x) * f[i];
ans = std:: min(ans, pre[i] + (p[ed].x - p[i].x) * 2);
cntb += p[i].tp;
f[i + 1] = cntb > i - cntb ? 3 : 1;
}
printf("%lld\n", ans);
return 0;
}
|
最大权值划分
思路
首先我们可以发现， 划分完后每段区间的极值必然就是区间的端点值， 不然的话极值在中间的话， 按极值为端点再把这个区间一分为二， 答案只可能变大而不会变小
于是我们得到极值必然是端点的性质， 我们将这个题转化为对每个$i$进行符号赋值， 赋成正数， 负数和零代表其贡献， 另外由于这是区间划分， 在处理每个$i$时， 我们要保证正负号的差距不能超过$1$， 这样赋值当然是会出现错误的， 但是错误的赋值方法得到的答案必然会比正确的答案更劣， 所有没有影响， 这也是把两个题放在一起的原因
代码
$f[i][0, 1, 2]$表示处理到$i$正负号差距为$0, 1, -1$时的最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #include <iostream>
#include <cstdio>
int n;
int a[1000006];
long long f[1000006][3];
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
f[1][0] = 0;
f[1][1] = a[1];
f[1][2] = -a[1];
for(int i = 2; i <= n; i ++)
{
f[i][0] = std:: max(f[i - 1][0], std:: max(f[i - 1][1] - a[i], f[i - 1][2] + a[i]));
f[i][1] = std:: max(f[i - 1][1], f[i - 1][0] + a[i]);
f[i][2] = std:: max(f[i - 1][2], f[i - 1][0] - a[i]);
}
printf("%lld\n", f[n][0]);
return 0;
}
|
总结
当可以对某些东西进行赋值， 并且不合法的方法一定比正解更劣时， 我们就可以随意赋值而不必在意赋值的合法性性