印刷网站开发的可行性报告,成都做网站建设公司,企业邮箱地址怎么填,做网站下载别人的图算不算侵权LuoguP5504 [JSOI2011]柠檬
题目描述
Solution
容易发现一个性质#xff1a;每一段划分区间的首尾两个元素相同。 因为倘若不相同的话其中至少一个元素也就不产生贡献#xff0c;将其划分在其他区间一定不会变劣。
因此就可以写出一个简单的O(n2)O(n^2)O(n2)的dpdpdp。 f…LuoguP5504 [JSOI2011]柠檬
题目描述
Solution
容易发现一个性质每一段划分区间的首尾两个元素相同。 因为倘若不相同的话其中至少一个元素也就不产生贡献将其划分在其他区间一定不会变劣。
因此就可以写出一个简单的O(n2)O(n^2)O(n2)的dpdpdp。 fifj−1(si−sj1)2(aiaj)f_if_{j-1}(s_i-s_j1)^2\;\;\;\;\;\;\;(a_ia_j) fifj−1(si−sj1)2(aiaj) 其中sis_isi表示在iii之前的与iii相同的元素的个数。
考虑决策单调性 设有j1j2ij_1j_2ij1j2iaj1aj2a_{j_1}a_{j_2}aj1aj2令getans(x,y)getans(x,y)getans(x,y)表示fx−1(sy−sx1)2f_{x-1}(s_y-s_x1)^2fx−1(sy−sx1)2。
若getans(j1,i)≥getans(j2,i)getans(j_1,i)\geq getans(j_2,i)getans(j1,i)≥getans(j2,i)则对于所有i′≥ii\geq ii′≥i都有getans(j1,i′)≥getans(j2,i′)getans(j_1,i)\geq getans(j_2,i)getans(j1,i′)≥getans(j2,i′)因为两者的增长都是平方级别的。
因此我们可以用单调栈维护这一过程。 对于每一种aia_iai开一个单调栈我们希望的是保证栈中元素的getans(...,i)getans(...,i)getans(...,i)始终递增。每次如果发现栈顶元素没有它下面一个元素优就弹栈。
但这并不是完全正确的随着iii的后移因为前面的元素增长快所以可能存在一个j1j2j3ij_1j_2j_3ij1j2j3i使得getans(j1,i)getans(j3,i)getans(j_1,i)getans(j_3,i)getans(j1,i)getans(j3,i)但getans(j2,i)getans(j3,i)getans(j_2,i)getans(j_3,i)getans(j2,i)getans(j3,i)。
因此我们还需要保证栈中每一个元素xxx超过上面一个元素yyy的时间小于yyy超过它上面的元素zzz的时间。
这个某个元素超过另一个元素的时间可以二分求得。
所以我们维护单调栈时额外添加一个判断getans(stack[top−2])getans(stack[top−1])getans(stack[top-2])getans(stack[top-1])getans(stack[top−2])getans(stack[top−1])的时间是否比getans(stack[top−1])getans(stack[top])getans(stack[top-1])getans(stack[top])getans(stack[top−1])getans(stack[top])的时间短即可。
时间复杂度O(nlgn)O(nlgn)O(nlgn)。
#include vector
#include list
#include map
#include set
#include deque
#include queue
#include stack
#include bitset
#include algorithm
#include functional
#include numeric
#include utility
#include sstream
#include iostream
#include iomanip
#include cstdio
#include cmath
#include cstdlib
#include cctype
#include string
#include cstring
#include ctime
#include cassert
#include string.h
//#include unordered_set
//#include unordered_map
//#include bits/stdc.h#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i(a);i(b);i)
#define fi first
#define se secondusing namespace std;templatetypename Tinline bool upmin(T x,T y) { return yx?xy,1:0; }
templatetypename Tinline bool upmax(T x,T y) { return xy?xy,1:0; }typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pairint,int PR;
typedef vectorint VI;const lod eps1e-11;
const lod piacos(-1);
const int oo130;
const ll loo1ll62;
const int mods998244353;
const int MAXN600005;
const int INF0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{int f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)(c^48); cgetchar(); }return x*f;
}
ll f[MAXN];
vectorint V[MAXN];
int a[MAXN],s[MAXN],cnt[MAXN],n;
ll Getans(int x,int y) { return f[x-1]1ll*a[x]*y*y; }
ll getans(int x,int y) { return f[x-1]1ll*a[x]*(s[y]-s[x]1)*(s[y]-s[x]1); }
int check(int x,int y)
{int ls[y],rn1;while (lr){int mid(lr)1;if (Getans(x,mid-s[x]1)Getans(y,mid-s[y]1)) rmid;else lmid1;}return r;
}
int main()
{nread();for (int i1;in;i) s[i]cnt[a[i]read()];f[0]0;for (int i1,sz;in;i){szV[a[i]].size()-1;while (sz1check(V[a[i]][sz-1],V[a[i]][sz])check(V[a[i]][sz],i)) V[a[i]].pop_back(),sz--;V[a[i]].PB(i),sz;while (sz1getans(V[a[i]][sz-1],i)getans(V[a[i]][sz],i)) V[a[i]].pop_back(),sz--;f[i]getans(V[a[i]][sz],i);}printf(%lld\n,f[n]);return 0;
}
