一道有前置题目的贪心。
总体看来不错，思维难度也是有的。
题目链接。
题意
现在有
盏台灯，你需要将它们中的
个点亮成红色，剩余的
个点亮成蓝色。
如果第 盏台灯和第 盏台灯颜色不同，那么你将会获得 的收益。
求最大收益。
题解
首先，我们不妨假设 。
因为如果 ，我们可以令
，显然答案不会变。
那么现在红色台灯的数量一定会小于等于蓝色台灯的数量。
那么我们就会有一个结论：
所有的最优方式中，一定存在一个方案，使得不会有任何两个红色台灯相邻摆放
考虑证明这个结论。
我们首先从左到右找到第一个极长的红色块 ，满足 。
假如此时 ，那么根据假设，第
个位置肯定是蓝色的台灯。
假如此时第
个位置没有台灯或者台灯是蓝色，我们直接将 和 上的颜色互换，答案显然会增加 。
否则，第
个位置以前肯定是若干个“单独”的红色台灯。
这个时候，找到
以左的，最靠右的，相邻的两个蓝色台灯。
如果可以找到，那么我们将这两个台灯以右的所有红色台灯，向左移一个位置·，这样子答案照样会增加，并且我们将第
个位置的红色台灯，挪到了第 个位置。
注意到这个时候 ，所以如果左边不能移动，那么右边按照同样的方法，肯定可以移动。
所以这个结论就是正确的。
这个时候我们就可以转化问题，成下面这个样子：
现在有一个长度为 的序列 ，满足 ，这里 。
现在你需要在上面选出
个点，使得这些点互不相邻，这个选点方案的价值为所有选的点 值的和。
求所有方案，权值的最大值。
你有没有发现，这个样子虽然转化了，但是好像和没有转化差不多，都是一样难做。
但是这道题是一道带悔贪心，并且有原题。
luoguP3620
上面的题只要做一下差分，就和我们转化后的题意一样了（并且上面这道题做法的第一步就是差分）。
代码
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
49
50
51
52
53
54
| #include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
using namespace std;
using ll=long long;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
int s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
priority_queue<pli>que;
bool vis[200001];
int in[200001];
int l[200001];
int r[200001];
ll s[200001];
int n,m;
int main()
{
n=read(),m=read(),m=min(m,n-m);
for(int i=1;i<n;i++) in[i]=read();
for(int i=1;i<n;i++)
{
s[i]=in[i]+in[i+1];
l[i]=i-1,r[i]=i+1;
que.push(pli(s[i],i));
}
ll ans=0;r[n]=n,s[0]=s[n]=-0x3f3f3f3f3f3f3fll;
for(int i=1;i<=m;i++)
{
while(vis[que.top().second]) que.pop();
int wh=que.top().second;que.pop();
ans+=s[wh],vis[l[wh]]=vis[r[wh]]=1;
s[wh]=s[l[wh]]+s[r[wh]]-s[wh];
l[wh]=l[l[wh]],r[wh]=r[r[wh]];
l[r[wh]]=r[l[wh]]=wh;
que.push(pli(s[wh],wh));
}
printf("%lld\n",ans);
return 0;
}
|
感谢观看！