正題

題目鏈接:https://www.luogu.com.cn/problem/CF573E

---

題目大意

給出一個長度為$n$的序列$a$，求它的一個子序列$b$，要求最大化
$$\sum _{i=1}^{|b|}{b}_i\times i$$

$1\le n\le 10^5,|a_i|\le 10^7$

---

解題思路

首先我們考慮最暴力的$dp$，設$f_{i,j}$表示到現在到$a$的第$i$個，然后選擇了$j$個時的最大答案，那么我們有
$$f_{i,j}=max\{f_{i?1,j},f_{i?1,j?1}+b_i\times j\}$$
然后發現這個$dp$很難進行維護，我們嘗試找下性質。
然后我沒找到去看題解發現確實是性質題，對于一個$i$，如果$f_{i,j}$從$f_{i,j?1}$轉移過來，那么$f_{i,j+1}$也一定是從$f_{i?1,j}$轉移過來的。

證明的話可以看這篇大佬的博客：https://www.luogu.com.cn/blog/Mrsrz/solution-cf573e

所以我們可以用一個平衡樹去維護每個$i$的$dp$值，然后我們就只需要二分出兩個轉移方式的中轉點$k$，然后對于前面的我們不變，對于后面的我們在區間前插入一個$f_{i,k?1}$，然后就是一個區間加等差序列的操作，用懶標記維護即可。

時間復雜度：$O(n{\log }^{2}n)$

如果在平衡樹上二分能做到$O(n\log n)$

當然還有另一種做法，考慮一個一個插入答案，能夠證明不停插入會使得當前貢獻最大的數也是最優的。

那么我們就只需要用分塊維護每一個數的新貢獻就好了。

時間復雜度：$O(n\sqrt{n})$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #define ll long long using namespace std; const ll N=1e5+10; ll n,cnt,rt,t[N][2],dat[N],siz[N]; ll w[N],lazy[N],lazy2[N],ans; ll Newp(ll val){w[++cnt]=val;dat[cnt]=rand();siz[cnt]=1;return cnt; } ll Cpy(ll x) {return Newp(w[x]);} void Update(ll x,ll val,ll dr){w[x]+=val*(siz[t[x][0]]+dr);lazy[x]+=val*dr;lazy2[x]+=val; } void PushDown(ll x){if(lazy[x]){if(t[x][0])w[t[x][0]]+=lazy[x],lazy[t[x][0]]+=lazy[x];if(t[x][1])w[t[x][1]]+=lazy[x],lazy[t[x][1]]+=lazy[x];lazy[x]=0;}if(lazy2[x]){if(t[x][0])Update(t[x][0],lazy2[x],0);if(t[x][1])Update(t[x][1],lazy2[x],siz[t[x][0]]+1);lazy2[x]=0;}return; } void PushUp(ll x){siz[x]=siz[t[x][0]]+siz[t[x][1]]+1;return;} void Split(ll &x,ll &y,ll p,ll val){if(!p){x=y=0;return;}PushDown(p);if(siz[t[p][0]]<=val)x=p,Split(t[x][1],y,t[p][1],val-siz[t[p][0]]-1);else y=p,Split(x,t[y][0],t[p][0],val);PushUp(p); } ll Merge(ll x,ll y){if(!x||!y)return x|y;PushDown(x);PushDown(y);if(dat[x]<dat[y]){t[x][1]=Merge(t[x][1],y);PushUp(x);return x;}else{t[y][0]=Merge(x,t[y][0]);PushUp(y);return y;} } ll GetVal(ll &rt,ll pos){ll x,y,z;Split(x,z,rt,pos);Split(x,y,x,pos-1);ll ans=w[y];x=Merge(x,y);rt=Merge(x,z);return ans; } void GetAns(ll x){if(!x)return;PushDown(x);ans=max(ans,w[x]);GetAns(t[x][0]);GetAns(t[x][1]);return; } bool check(ll x,ll w){ll a=GetVal(rt,x);ll b=GetVal(rt,x-1);return a>b+x*w; } signed main() {scanf("%lld",&n);rt=Newp(0);rt=Merge(rt,Newp(-1e18));for(ll i=1,k;i<=n;i++){scanf("%lld",&k);ll l=1,r=i;while(l<=r){ll mid=(l+r)>>1;if(check(mid,k))l=mid+1;else r=mid-1;}ll x,y,z,d;Split(x,z,rt,l-1);Split(z,d,z,n-1);Split(x,y,x,l-2);d=Cpy(y);z=Merge(d,z);Update(z,k,l);rt=x;rt=Merge(rt,y);rt=Merge(rt,z);}GetAns(rt);printf("%lld\n",ans);return 0; }```

總結

以上是生活随笔為你收集整理的CF573E-Bear and Bowling【dp,平衡树】的全部內容，希望文章能夠幫你解決所遇到的問題。

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