正題

題目鏈接: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("%lld\n",ans); }

總結

以上是生活随笔為你收集整理的ATcoder-[AGC048B]Bracket Score【结论,贪心】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。