网站开发技术视频教程,网络推广怎么收费,制作网页的基本代码,网站开发薪水一般多少正题
题目链接:https://www.luogu.com.cn/problem/CF573E 题目大意
给出一个长度为nnn的序列aaa#xff0c;求它的一个子序列bbb#xff0c;要求最大化 ∑i1∣b∣bii\sum_{i1}^{|b|}b_i\times ii1∑∣b∣bii 1≤n≤105,∣ai∣≤1071\leq n\leq 10^5,|a_i|\leq 10^71≤n…正题
题目链接:https://www.luogu.com.cn/problem/CF573E 题目大意
给出一个长度为nnn的序列aaa求它的一个子序列bbb要求最大化 ∑i1∣b∣bi×i\sum_{i1}^{|b|}b_i\times ii1∑∣b∣bi×i
1≤n≤105,∣ai∣≤1071\leq n\leq 10^5,|a_i|\leq 10^71≤n≤105,∣ai∣≤107 解题思路
首先我们考虑最暴力的dpdpdp设fi,jf_{i,j}fi,j表示到现在到aaa的第iii个然后选择了jjj个时的最大答案那么我们有 fi,jmax{fi−1,j,fi−1,j−1bi×j}f_{i,j}max\{f_{i-1,j},f_{i-1,j-1}b_i\times j\}fi,jmax{fi−1,j,fi−1,j−1bi×j} 然后发现这个dpdpdp很难进行维护我们尝试找下性质。 然后我没找到去看题解发现确实是性质题对于一个iii如果fi,jf_{i,j}fi,j从fi,j−1f_{i,j-1}fi,j−1转移过来那么fi,j1f_{i,j1}fi,j1也一定是从fi−1,jf_{i-1,j}fi−1,j转移过来的。
证明的话可以看这篇大佬的博客https://www.luogu.com.cn/blog/Mrsrz/solution-cf573e
所以我们可以用一个平衡树去维护每个iii的dpdpdp值然后我们就只需要二分出两个转移方式的中转点kkk然后对于前面的我们不变对于后面的我们在区间前插入一个fi,k−1f_{i,k-1}fi,k−1然后就是一个区间加等差序列的操作用懒标记维护即可。
时间复杂度O(nlog2n)O(n\log^2 n)O(nlog2n)
如果在平衡树上二分能做到O(nlogn)O(n\log n)O(nlogn)
当然还有另一种做法考虑一个一个插入答案能够证明不停插入会使得当前贡献最大的数也是最优的。
那么我们就只需要用分块维护每一个数的新贡献就好了。
时间复杂度O(nn)O(n\sqrt n)O(nn) code
#includecstdio
#includecstring
#includealgorithm
#includevector
#define ll long long
using namespace std;
const ll N1e510;
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){xy0;return;}PushDown(p);if(siz[t[p][0]]val)xp,Split(t[x][1],y,t[p][1],val-siz[t[p][0]]-1);else yp,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 answ[y];xMerge(x,y);rtMerge(x,z);return ans;
}
void GetAns(ll x){if(!x)return;PushDown(x);ansmax(ans,w[x]);GetAns(t[x][0]);GetAns(t[x][1]);return;
}
bool check(ll x,ll w){ll aGetVal(rt,x);ll bGetVal(rt,x-1);return abx*w;
}
signed main()
{scanf(%lld,n);rtNewp(0);rtMerge(rt,Newp(-1e18));for(ll i1,k;in;i){scanf(%lld,k);ll l1,ri;while(lr){ll mid(lr)1;if(check(mid,k))lmid1;else rmid-1;}ll x,y,z,d;Split(x,z,rt,l-1);Split(z,d,z,n-1);Split(x,y,x,l-2);dCpy(y);zMerge(d,z);Update(z,k,l);rtx;rtMerge(rt,y);rtMerge(rt,z);}GetAns(rt);printf(%lld\n,ans);return 0;
}
相关文章：
