正題

題目鏈接:https://www.luogu.org/problem/P3470

---

題目大意

一個(gè)$+?$序列，$+$表示$1$，$?$表示$?1$。$s_i$表示到第$i$個(gè)的前綴和，要求
$$q+s_n=p且q+s_i\ge 0(i\in [1..n])$$

然后有以下操作

消耗$x$將一位取反

消耗$y$將最后一位丟到最前面

求最小消耗

---

解題思路

先不考慮操作2
若已經(jīng)滿足了$q+s_n=p$，那么答案顯然為$max\{?q?s_i,0\}?2?x$
然后我們考慮那若不同呢，我們考慮將兩個(gè)可以合并在一起計(jì)算
答案就是$$(\frac{max\{?q?s_i,0\}}{2}+|\frac{max\{?q?s_i,0\}?(q?p+s_n)}{2}|)?x$$

上的都可以$O(1)$的時(shí)間內(nèi)計(jì)算，所以我們暴力枚舉轉(zhuǎn)了多少次

這里的$max\{?q?s_i,0\}$我是用線段樹進(jìn)行維護(hù)的，時(shí)間復(fù)雜度$O(n\log n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1e6+100; struct Tree_node{int l,r,w,lazy; }; int n,p,q,x,y,s[N],k,z,ans; char a[N]; struct Seg_Tree{Tree_node t[N*4];void Build(int x,int l,int r){t[x].l=l;t[x].r=r;if(l==r){t[x].w=s[l];return;}int mid=(l+r)/2;Build(x*2,l,mid);Build(x*2+1,mid+1,r);t[x].w=max(t[x*2].w,t[x*2+1].w);}void DownData(int x){if(!t[x].lazy) return;t[x*2].lazy+=t[x].lazy;t[x*2+1].lazy+=t[x].lazy;t[x*2].w+=t[x].lazy;t[x*2+1].w+=t[x].lazy;t[x].lazy=0;return;}void Change(int x,int l,int r,int val){if(t[x].l==l&&t[x].r==r){t[x].w+=val;t[x].lazy+=val;return;}DownData(x);int mid=(t[x].l+t[x].r)/2;if(r<=mid) Change(x*2,l,r,val);else if(l>mid) Change(x*2+1,l,r,val);else Change(x*2,l,mid,val),Change(x*2+1,mid+1,r,val);} }Tree; int main() {freopen("data.in","r",stdin);freopen("data.out","w",stdout);scanf("%d%d%d%d%d",&n,&p,&q,&x,&y);scanf("%s",a+1);n=strlen(a+1);for(int i=1;i<=n;i++)s[i]=s[i-1]+(a[i]=='+'?-1:1);Tree.Build(1,1,n);k=(q-p+s[n])/2;ans=2e9;for(int i=0;i<n;i++){if(i*y>ans) break;if(k>=0) ans=min(ans,i*y+max(Tree.t[1].w-p-k*2,0)*2*x+abs(k)*x);else ans=min(ans,i*y+max(Tree.t[1].w-p,0)*2*x+max(abs(k)-max(Tree.t[1].w-p,0),0)*x);Tree.Change(1,n-i,n-i,-s[n-i]-z);Tree.Change(1,1,n,(a[n-i]=='+'?-1:1));z+=(a[n-i]=='+'?-1:1);}printf("%d",ans); }

總結(jié)

以上是生活随笔為你收集整理的P3470 [POI2008]BBB-BBB【线段树,贪心】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。