正题

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

题目大意

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

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

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

解题思路

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

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

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

时间复杂度$O(n\log n)$

$code$

#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);
}

最后

以上就是有魅力橘子为你收集整理的ATcoder-[AGC048B]Bracket Score【结论,贪心】正题的全部内容，希望文章能够帮你解决ATcoder-[AGC048B]Bracket Score【结论,贪心】正题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。