Thoughts:
First find the\(a\) prefixes and arrays of\(s\)。
Consider dynamic programming such that\(dp_{i,j}\) expressed in terms of\(i\) at the end, and at the end with\(j\) The minimum answer for a group of individuals is the state transfer equation:
The plain direct transfer is\(O(N^3)\) You can get a good 36pts for that.I won't bother giving the code.。
Consider optimization, for finding the smallest one\(k\)makes\(s_{i-j}-s_{i-j-k} > s_i - s_{i-j}\), then the state transfer equation is:
The latter string can be prefixed and preprocessed well in advance, and the complexity is now in finding the\(k\) On, noting that\(s_{i,j} - s_{i-j-k}\) is monotonic, then direct bisection is sufficient.
The time complexity is optimized to\(O(N^2 \log N)\)。
$O(N^2 \log N)$ Code.
#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
using namespace std;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const ll N=5050,INF=4e18;
inline ll read(){
ll x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')
f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
inline void write(ll x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9)
write(x/10);
putchar(x%10+'0');
}
bool op;
ll n,l,r,h,t,ans=INF;
ll s[N],dp[N][N],f[N][N];
ll get(ll l,ll r){
if(l>r)
return 0;
if(!l)
return s[r];
return s[r]-s[l-1];
}
bool End;
int main(){
n=read(),op=read();
for(int i=1;i<=n;i++)
s[i]=s[i-1]+read();
dp[1][0]=f[1][0]=INF;
dp[1][1]=f[1][1]=s[1]*s[1];
for(int i=2;i<=n;i++){
f[i][0]=dp[i][0]=INF;
for(int j=1;j<=i;j++){
l=1,r=i-j,t=0,h=get(i-j+1,i);
if(s[i-j]<=h)
t=i-j+1;
else{
while(l<=r){
ll mid=(l+r)>>1;
if(get(i-j-mid+1,i-j)>h){
t=mid;
r=mid-1;
}
else
l=mid+1;
}
}
dp[i][j]=f[i-j][t-1]+h*h;
f[i][j]=min(f[i][j-1],dp[i][j]);
}
}
for(int i=1;i<=n;i++)
ans=min(ans,dp[n][i]);
write(ans);
cerr<<'\n'<<abs(&Begin-&End)/1048576<<"MB";
return 0;
}
Afterwards we can find that if\(j\) is monoincreasing, the\(i-j-k+1\) is single descending, then we have direct access to the\(k\) It is sufficient to perform a pointer walk, and the time complexity is optimized to\(O(N^2)\)The result is a good 64pts.
$O(N^2)$ Code.
#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
using namespace std;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const ll N=5050,INF=4e18;
inline ll read(){
ll x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')
f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
inline void write(ll x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9)
write(x/10);
putchar(x%10+'0');
}
bool op;
ll n,t,h,sum,ans=INF;
ll s[N],a[N],dp[N][N],f[N][N];
ll get(ll l,ll r){
if(l>r)
return 0;
if(!l)
return s[r];
return s[r]-s[l-1];
}
bool End;
int main(){
n=read(),op=read();
for(int i=1;i<=n;i++){
a[i]=read();
s[i]=s[i-1]+a[i];
}
dp[1][0]=f[1][0]=INF;
dp[1][1]=f[1][1]=s[1]*s[1];
for(int i=2;i<=n;i++){
f[i][0]=dp[i][0]=INF;
t=i-1,sum=a[i-1];
for(int j=1;j<=i;j++){
ll h=get(i-j+1,i);
while(sum<=h&&t){
t--;
sum+=a[t];
}
dp[i][j]=f[i-j][i-j-t]+h*h;
f[i][j]=min(f[i][j-1],dp[i][j]);
sum-=a[i-j];
}
}
for(int i=1;i<=n;i++)
ans=min(ans,dp[n][i]);
write(ans);
cerr<<'\n'<<abs(&Begin-&End)/1048576<<"MB";
return 0;
}
Because the number of states in our kind of dp have reached the\(N^2\), and so considered finding something of that nature.
Easy to hit the meter found inLegal situationunder which the\(dp_{i,j} \le dp_{i,j+1}\)。
Then we can find each position\(i\)For the record.\(f_i\) indicate\(\min dp_{i,j}\)and the last paragraph is\([g_i,i]\), then the state transfer equation is:
At this point we'll move the state time to\(O(N)\) level, now consider to optimize the state transfer equation.
$O(N)$ Status Code
#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
using namespace std;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const ll N=5e5+10,INF=4e18;
inline ll read(){
ll x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')
f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
inline void write(ll x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9)
write(x/10);
putchar(x%10+'0');
}
bool op;
ll n,t,h,ans=INF;
ll s[N],a[N],f[N],g[N];
ll get(ll l,ll r){
if(l>r)
return 0;
if(l<0)
return s[r];
return s[r]-s[l-1];
}
bool End;
int main(){
n=read(),op=read();
for(int i=1;i<=n;i++){
a[i]=read();
s[i]=s[i-1]+a[i];
f[i]=INF;
}
g[1]=1;
f[0]=g[0]=0;
f[1]=s[1]*s[1];
for(int i=2;i<=n;i++){
for(int j=0;j<i;j++){
h=get(g[j],j),t=get(j+1,i);
if(h>t)
continue;
if(f[j]+t*t<f[i]){
f[i]=f[j]+t*t;
g[i]=j+1;
}
}
}
write(f[n]);
cerr<<'\n'<<abs(&Begin-&End)/1048576<<"MB";
return 0;
}
It is easy to notice that when\(j\) The value of this equation is minimized when it is maximized, so we need to find a maximal\(j\) fulfillment\(s_j-s_{g_j-1} \le s_i - s_j\), ie:
perceive\(s_i\) single increment, we can maintain a\(2s_j - s_{g_j-1}\) single-incremented monotonic queue, and then find the last one in this queue that satisfies the condition\(j\)So.\(j\) Previous counts could not contribute to the answer, ejecting it.
This way each number is popped at most once, with a time complexity of\(O(N)\)。
Full Code:
#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
using namespace std;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
typedef __int128 __;
bool Begin;
const ll N=4e7+5,mod=1ll<<30;
inline ll read(){
ll x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')
f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
inline void write(__ x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9)
write(x/10);
putchar(x%10+'0');
}
__ t,ans;
bool op;
int n,head=1,tail=0;
ll s[N],g[N];
int Q[N];
inline void Read(){
ll x,y,z,m,p,l,r,pre=0;
x=read(),y=read(),z=read(),s[1]=read(),s[2]=read(),m=read();
for(int i=3;i<=n;i++)
s[i]=(x*s[i-1]+y*s[i-2]+z)%mod;
for(int i=1;i<=m;i++){
p=read(),l=read(),r=read();
for(int j=pre+1;j<=p;j++)
s[j]=(s[j]%(r-l+1))+l;
pre=p;
}
}
inline ll get(int l,int r){
if(l>r)
return 0;
if(l<1)
return s[r];
return s[r]-s[l-1];
}
inline ll date(ll x){
return 2ll*s[x]-s[g[x]-1];
}
bool End;
int main(){
n=read(),op=read();
if(op==1)
Read();
else{
for(int i=1;i<=n;i++)
s[i]=read();
}
for(int i=1;i<=n;i++)
s[i]+=s[i-1];
g[1]=1,g[0]=0;
Q[++tail]=0,Q[++tail]=1;
for(int i=2;i<=n;i++){
while(date(Q[head+1])<=s[i]&&head+1<=tail)
head++;
g[i]=Q[head]+1;
t=get(g[i],i);
while(date(i)<=date(Q[tail])&&tail>=head)
tail--;
Q[++tail]=i;
}
for(int i=n;i>=1;i=g[i]-1)
ans+=(__)(s[i]-s[g[i]-1])*(s[i]-s[g[i]-1]);
write(ans);
cerr<<'\n'<<abs(&Begin-&End)/1048576<<"MB";
return 0;
}