ATcoder-[AGC048B]Bracket Score【结论,贪心】正题

165 阅读 0 评论 109 点赞

我是靠谱客的博主有魅力橘子，这篇文章主要介绍ATcoder-[AGC048B]Bracket Score【结论,贪心】正题，现在分享给大家，希望可以做个参考。

正题

题目链接:https://atcoder.jp/contests/agc048/tasks/agc048_b

题目大意

长度为 $n$ 的合法括号序列可以包含 $[. . .]$ 和 $(. . .)$ 。

如果在第 $i$ 个位置是 $^{'} (^{'}$ 或者 $^{'})^{'}$ 那么可以获得 $a_i$ 的权值，否则获得 $b_i$ 的权值。

求一个合法的括号序列使得权值最大。

解题思路

首先对于每对匹配的括号肯定是一奇一偶的，有一个结论就是只要两种括号的奇和偶数上括号的个数相同，那么就一定有一种合法匹配。

大致的理解方法就是，对于每一种方案至少存在一对相邻的同种括号，否则就不满足以上性质，然后就可以将这对括号删去。重复以上过程就可以证明该结论

那么考虑贪心选取，对于每个位置我们先默认选择小括号，那么如果转换的话就会获得 $w_i=a_i-b_i$ 的价值。然后每次选取一奇一偶的 $w_i$ ，把奇偶的 $w_i$ 分开排序选取即可。

时间复杂度 $O (n lo g n)$

$c o d e$

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;
const ll N=1e5+10;
ll n,a[N],b[N],sum,ans;
vector<ll > v[2];
int main()
{
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++)scanf("%lld",&a[i]);
    for(ll i=1;i<=n;i++)scanf("%lld",&b[i]),sum+=b[i];
    for(ll i=1;i<=n;i++)
        v[i&1].push_back(a[i]-b[i]);
    sort(v[0].begin(),v[0].end());
    sort(v[1].begin(),v[1].end());
    ans=sum;
    for(ll i=v[0].size()-1;i>=0;i--)
        sum+=v[0][i]+v[1][i],ans=max(ans,sum);
    printf("%lldn",ans);
}