网上还没有题解,随便写写,顺便庆祝一下RANK1
$O(n^{2})$的DP很好想,用s[i]表示a[i]在i位置上的出现是第几次$dp[i]=max(dp[j-1]+(s[i]-s[j]+1)^{2}*a[i])$
非常显然这个东西是有单调性的,s[i]变大的时候相对较小的j会变优。所以我们可以写一个类似于斜率的东西。
$(s-s[i])^2*x+dp[i-1]>=(s-s[j])^2*x+dp[j-1]$
$(2*s-s[i]-s[j])*(s[j]-s[i])*x>dp[j-1]-dp[i-1]-1$
$2*s>(dp[j-1]-dp[i-1]-1)/x/(s[j]-s[i])+s[i]+s[j]$
对于每个a[i]都维护一个栈,保持决策最优性就行了。这里我是用链表维护的。
#include<cstdio> #include<queue> using namespace std; int n; int a[100005],head[10005],Head[100005],nex[100005],s[100005]; long long dp[100005]; inline int read(){ int ret=0;char c=getchar(); while((c>'9')||(c<'0'))c=getchar(); while((c>='0')&&(c<='9'))ret=(ret<<1)+(ret<<3)+c-'0',c=getchar(); return ret; } inline long long check(int i,int j,int x){return 1LL*(s[j]-s[i]+1)*(s[j]-s[i]+1)*x+dp[i-1];} inline long long work(int i,int j,int x){return (dp[j-1]-dp[i-1]-1)/x/(s[j]-s[i])+s[i]+s[j];} int main(){ n=read(); for(int i=1;i<=n;i++){ int x=read();s[i]=s[Head[x]]+1;Head[x]=i; if((head[x]==0)||(check(head[x],i,x)<check(i,i,x))){ while((nex[head[x]])&&(work(head[x],i,x)>=work(nex[head[x]],head[x],x)))head[x]=nex[head[x]]; nex[i]=head[x];head[x]=i; } while((nex[head[x]])&&(check(nex[head[x]],i,x)>check(head[x],i,x)))head[x]=nex[head[x]]; dp[i]=check(head[x],i,x); } printf("%lld",dp[n]); }
2022年8月25日 18:32
Meghalaya Board Model Paper 2023 Class 7 Pdf Download with Answers for Bengali Medium, English Medium, Hindi Medium, Urdu Medium & Students for Small Answers, Long Answer, Very Long Answer Questions, and Essay Type MBOSE Model Paper Class 7 Questions to Term1 & Term2 Exams at official website. New Exam Scheme or Question Pattern for Sammittive Assignment Exams (SA1 & SA2): Very Long Answer (VLA), Long Answer (LA), Small Answer (SA), Very Small Answer (VSA), Single Answer, Multiple Choice and etc.