Statement
Solve
8pts ，暴力枚举分界点 \(O(2^nn)\)
36pts，\(O(n^3)\) \(\text{DP}\)
我们设 \(f[i][j]\) 表示前 \(i\) 个数，最后一段开始节点 \(j\) 的最小代价
设 \(sum[i]=\sum_{j=1}^ia[j]\)
那么，\(f[i][j]=min\{f[j-1][k]+(sum[i]-sum[j-1])^2\}\)
初态：\(f[i][1]=s[i]^2\) 答案：\(\sum_{i=1}^n f[n][i]\)
64pts, \(O(n^2)\) 贪心
首先，\((\sum_{i=1}^ka_i)^2\geq\sum_{i=1}^ka_i^2\) ，这个引导我们多分段
然后，我们知道一个显然的结论：最后一段尽量小的答案更优
简单证明：
假设 \(sum1+sum2<sum3,sum2<sum1\) ，考虑红色段应该分在哪边
（这个假设实际上是保证了 可以分在左边+需要分）
左边：\((sum1+sum2)^2+sum3^2\)
右边：\((sum3+sum2)^2+sum1^2\)
右 \(-\) 左：\(2\times sum2(sum3-sum1)\)
因为我们假设 \(sum1+sum2<sum3\) ，所以 \(sum3-sum1>0\)
也就是说，分在右边比分在左边的代价高，所以，最后一段应该尽量小。
——
我们把这个贪心结论融合入刚刚的 \(dp\)
此时，上一段的起点 \(k\) 确定，直接更新即可
这里，设 \(f[i]\) 表示前 \(i\) 个数字分段的最小代价，\(pos[i]\) 表示以 \(i\) 结尾的段的最大开头
for(int i=2;i<=n;++i)
for(int j=1;j<i;++j)
if(f[i]>f[j]+(sum[i]-sum[j])*(sum[i]-sum[j])&&sum[i]-sum[j]>=sum[j]-sum[pos[j]])//值得更新且可以更新
f[i]=f[j]+(sum[i]-sum[j])*(sum[i]-sum[j]),pos[i]=j;
因为我们是顺序枚举 \(j\) ，所以最后 \(pos[i]\) 尽量大，段值尽量小
100pts
我们可以在挖掘一下之前的贪心
显然，\(f[j]\) 能更新 \(f[i]\) 的一个条件是 \(sum[i]-sum[j]\geq sum[j]-sum[pos[j]]\)
移项：\(sum[i]\geq 2\times sum[j]-sum[pos[j]]\)
设 \(calc(i)=2\times sum[i]-sum[pos[i]]\)
那么我们要找的其实就是满足上述条件的最大的一个 \(j\)
因为 \(sum\) 单调上升，发现决策集合单调增长
考虑单调队列维护一个递增下标序列（决策集合）
-
只要 \(calc[q[l+1]]<=sum[i]\) ，那么 \(l++\) ，因为我们找的是最大的 \(j\) 来更新 \(i\)
-
用 \(q[l]\) 更新 \(i\)
-
只要 \(calc[q[r]]>=calc[i]\)，那么 \(r--\) ,因为 \(i\) 相对于 \(q[r]\) 显然是一个更好的决策，不仅比他靠后，而且值更小，更容易满足条件去更新其他的
-
\(i\) 入队
int l=1,r=1;
//q[1]=0;
for(int i=1;i<=n;++i){
while(l<r&&calc(q[l+1])<=sum[i])l++;//因为我们要用 q[l] 更新，所以比较下一位
f[i]=f[q[l]]+(sum[i]-sum[q[l]])*(sum[i]-sum[q[l]]);
while(l<=r&&calc(q[r])>=calc(i))r--;
q[++r]=i;
}
——
假装这样就可以了
但这样即使开 \(\_\_int128\) 也只有 \(88pts\)
我们需要高精度。
考虑到如果不压位的话会爆空间 ，所以我们还需要压位高精。
虽然这个复杂度是 \(O(n)\) 的，但是高精度还有一点常数，\(n\) 卡得太死啦，我们还要卡常
Code
#include<bits/stdc++.h>
#define max(x,y) x>y?x:y
using namespace std;
typedef unsigned long long ull;
const int mod = (1<<30)-1,base = 1e9;
const int N = 4e7+3, M = 1e5+3;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
int read(){
int val=0;char c=gc();
while(!isdigit(c))c=gc();
while(isdigit(c))val=val*10+(c^48),c=gc();
return val;
}
struct bigint{
int len;
ull num[4];
bigint operator+(const bigint&rhs)const{
bigint res;ull p=0;
memset(res.num,0,sizeof(res.num));
res.len=max(len,rhs.len);
for(int i=0;i<res.len;++i){
res.num[i]=num[i]+rhs.num[i]+p;
p=res.num[i]/base;
res.num[i]-=p*base;
}
if(p)res.num[res.len++]=p;
return res;
}
}ans;
int pos[N],b[N],q[N],p[M];
int n,type,z,m,l,r;
ull s[N],x,y;
ull calc(int x){
return (s[x]<<1)-s[pos[x]];
}
int main(){
n=read(),type=read();
if(type){
x=read();y=read();z=read();b[1]=read();b[2]=read();m=read();
for(int i=3;i<=n;i++)b[i]=((x*b[i-1]&mod)+(y*b[i-2]&mod)+ z)&mod;
for(int j=1;j<=m;++j){
p[j]=read(),l=read(),r=read();
for(int i=p[j-1]+1,a;i<=p[j];s[i]=s[i-1]+a,++i)
a=b[i]%(r-l+1)+l;
}
}else for(int i=1,a;i<=n;s[i]=s[i-1]+a,++i)a=read();
int l=1,r=1;
for(int i=1;i<=n;++i){
while(l<r&&calc(q[l+1])<=s[i])l++;//
pos[i]=q[l];
while(l<=r&&calc(q[r])>=calc(i))r--;//
q[++r]=i;
}
ans.len=0;
for(int i=n;i;i=pos[i]){
bigint tmp,res;ull val=s[i]-s[pos[i]];tmp.len=0;
while(val)tmp.num[tmp.len++]=val%base,val/=base;
memset(res.num,0,sizeof(res.num));
res.len=(tmp.len<<1)-1;ull p=0;
for(int j=0;j<tmp.len;++j)
for(int k=0;k<tmp.len;++k)
res.num[j+k]+=tmp.num[j]*tmp.num[k];
for(int j=0;j<res.len;++j){
res.num[j]+=p;
p=res.num[j]/base;
res.num[j]-=base*p;
}
while(p)res.num[res.len++]=p%base,p/=base;
ans=ans+res;
}
printf("%llu",ans.num[ans.len-1]);
for(int i=ans.len-2;~i;--i)
printf("%09llu",ans.num[i]);
return 0;
}