交互做的不好的网站,前端开发简历模板,具有价值的网站制作,梅州seo正题 题目大意
定义函数f(x)Ax3Bx2CxDf(x)Ax^3Bx^2CxDf(x)Ax3Bx2CxD 然后给出一个序列#xff0c;要求按顺序分成若干段。对于一段[L..R][L..R][L..R]#xff0c;贡献为f(min{ai}(i∈[L..R]))f(min\{a_i\}(i\in[L..R]))f(min{ai}(i∈[L..R])) 然后要求所有段的贡献之和最大…正题 题目大意
定义函数f(x)Ax3Bx2CxDf(x)Ax^3Bx^2CxDf(x)Ax3Bx2CxD 然后给出一个序列要求按顺序分成若干段。对于一段[L..R][L..R][L..R]贡献为f(min{ai}(i∈[L..R]))f(min\{a_i\}(i\in[L..R]))f(min{ai}(i∈[L..R])) 然后要求所有段的贡献之和最大。 解题思路
我们考虑dpdpdp设gig_igi表示将1∼i1\sim i1∼i分成若干段时的贡献那么我们有gigjwj1,i(jlt;i)g_ig_jw_{j1,i}(jlt; i)gigjwj1,i(ji) (wl,rw_{l,r}wl,r表示l∼rl\sim rl∼r这段范围的贡献)
但是时间复杂度为O(n2)O(n^2)O(n2)显然不能胜任本题。
然后我们需要考虑用数据结构优化我们发现对于每个aia_iai但计算到gig_igi或以后时它能影响的一定是k∼ik\sim ik∼i这段范围。那我们对于每个aia_iai我们都计算出这个范围我们发现这个范围其实就是在它前面的比它大的且与它最近的一个数这个我们可以用双端链表O(nlogn)O(n\ log\ n)O(n log n)进行计算。
然后我们枚举kkk然后用线段树维护gif(min{aj}(j∈[i..k]))g_{i}f(min\{a_{j}\}(j\in[i..k]))gif(min{aj}(j∈[i..k]))的最大值即可。
时间复杂度O(nlogn)O(n\log n)O(nlogn) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N2e5100,inf1e18;
struct Tree_node{ll w,lazy;
};
struct Seq_node{Tree_node t[N*4]; void Build(ll x,ll l,ll r){t[x].lazy-inf;if(lr){t[x].w-inf;return;}ll mid(lr)/2;Build(x*2,l,mid);Build(x*21,mid1,r);t[x].wmax(t[x*2].w,t[x*21].w);}void downdata(ll x){if(t[x].lazy-inf) return;t[x*2].wt[x*21].wt[x*2].lazyt[x*21].lazyt[x].lazy; t[x].lazy-inf;}void Change(ll x,ll l,ll r,ll w,ll L,ll R){if(lLrR){t[x].ww;t[x].lazyw;return;}downdata(x);ll mid(LR)/2;if(rmid) Change(x*2,l,r,w,L,mid);else if(lmid) Change(x*21,l,r,w,mid1,R);else Change(x*2,l,mid,w,L,mid),Change(x*21,mid1,r,w,mid1,R);t[x].wmax(t[x*2].w,t[x*21].w);}ll Ask(ll x,ll l,ll r,ll L,ll R){if(lLrR)return t[x].w;downdata(x);ll mid(LR)/2;if(rmid) return Ask(x*2,l,r,L,mid);if(lmid) return Ask(x*21,l,r,mid1,R);return max(Ask(x*2,l,mid,L,mid),Ask(x*21,mid1,r,mid1,R));}
}T,T2;
ll n,A,B,C,D,prev[N],next[N],id[N],last[N],f[N],ans,a[N];
bool cMp(ll x,ll y)
{return a[x]a[y];}
ll Val(ll x)
{return A*x*x*xB*x*xC*xD;}
int main()
{//freopen(min.in,r,stdin);//freopen(min.out,w,stdout);scanf(%lld%lld%lld%lld%lld,n,A,B,C,D);for(ll i1;in;i){scanf(%lld,a[i]);id[i]i;}for(ll i1;in;i)prev[i]i-1,next[i]i1;sort(id1,id1n,cMp);for(ll i1;in;i){ll xid[i];last[x]prev[x];prev[next[x]]prev[x];next[prev[x]]next[x];}T.Build(1,0,n);T2.Build(1,0,n);T.Change(1,0,0,0,0,n);T2.Change(1,0,0,0,0,n);for(ll i1;in;i){ll valT2.Ask(1,last[i],i,0,n);T.Change(1,last[i],i,valVal(a[i]),0,n);ansT.t[1].w;T2.Change(1,i,i,ans,0,n);}printf(%lld,ans);
}
