2022适合小学生的简短新闻摘抄,沈阳seo团队,佛山专业外贸网站建设,免费模板网站都有什么区别正题
题目链接:http://noi.ac/problem/2139 题目大意
给出nnn个数字的序列aia_iai。然后选出一个不降子序列最大化子序列的aia_iai和减去没有任何一个数被选中的区间数量。 1≤n≤106,1≤ai≤1081\leq n\leq 10^6,1\leq a_i\leq 10^81≤n≤106,1≤ai≤108 解题思路
嗯…正题
题目链接:http://noi.ac/problem/2139 题目大意
给出nnn个数字的序列aia_iai。然后选出一个不降子序列最大化子序列的aia_iai和减去没有任何一个数被选中的区间数量。
1≤n≤106,1≤ai≤1081\leq n\leq 10^6,1\leq a_i\leq 10^81≤n≤106,1≤ai≤108 解题思路
嗯考虑朴素的dpdpdp方程设fif_ifi表示以iii为末尾的值就有 fifjai(i−j−1)(i−j)2f_if_ja_i\frac{(i-j-1)(i-j)}{2}fifjai2(i−j−1)(i−j) 然后展开整理一下都乘二就是 fifj2aii2−ij2j−2ij(aj≤ai,ji)f_if_j2a_ii^2-ij^2j-2ij(a_j\leq a_i,ji)fifj2aii2−ij2j−2ij(aj≤ai,ji)
除了aj≤aia_j\leq a_iaj≤ai就是一个标准的斜率优化式子了
然后这个东西其实挺好搞的因为多一个限制直接上CDQCDQCDQ就好了但是每次左边要归并排序这样时间复杂度就是O(nlogn)O(n\log n)O(nlogn)的了
但其实还有更暴力的做法因为既然一个CDQCDQCDQ能做到那么找些数据结构之类的也肯定能做到。
对于树状数组上每个节点维护一个凸壳然后暴力查询就好了
时间复杂度O(nlogn)O(n\log n)O(nlogn) code
#includecstdio
#includecstring
#includealgorithm
#includevector
#define ll long long
#define lowbit(x) (x-x)
using namespace std;
const ll N1e610;
ll n,m,a[N],b[N],l[N],r[N],f[N],k[N];
vectorll q[N];
ll calc(ll i,ll j)
{return k[i]2*i*j;}
void Change(ll x,ll i){while(xm){while(l[x]r[x](k[i]-k[q[x][r[x]]])*(q[x][r[x]]-q[x][r[x]-1])(k[q[x][r[x]]]-k[q[x][r[x]-1]])*(i-q[x][r[x]]))r[x]--,q[x].pop_back();q[x].push_back(i);r[x];xlowbit(x);}return;
}
ll Ask(ll x,ll i){ll ans-1e18;while(x){while(l[x]r[x]calc(q[x][l[x]],i)calc(q[x][l[x]1],i))l[x];if(l[x]r[x])ansmax(ans,calc(q[x][l[x]],i));x-lowbit(x);}return ans;
}
signed main()
{scanf(%lld,n);for(ll i1;in;i)scanf(%lld,a[i]),b[i]a[i];sort(b1,b1n);munique(b1,b1n)-b-1;for(ll i1;im;i)r[i]-1;Change(1,0);for(ll i1;in;i){ll xlower_bound(b1,b1m,a[i])-b;f[i]Ask(x,i)2*a[i]-i*ii;k[i]f[i]-i*i-i;Change(x,i);}ll ans-1e18;for(ll i1;in;i)ansmax(ans,f[i]/2-(n-i1)*(n-i)/2);printf(%lld\n,ans);return 0;
}
