乱搞笔记 by ChanHacker
我的博客：
https://ch66.cf/ 欢迎来踩
这题瞎写就可以了，大暴力，单调栈都不需要。
我还以为有多难呢
我们设$ f[i] $为前i个数，$O(n)$的枚举$j$，$i-j$的区间合并，复杂度$O(n^2)$
然后找规律。。。。
发现当$j<=i$时，决策i一定大于等于决策j
于是$O(n)$算法诞生了
下面是代码（考试的时候没打高精）
#include<bits/stdc++.h>
using namespace std;
long long read() {
register long long x=1,ans=0;register char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') x*=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){ans=(ans<<3)+(ans<<1)+ch-48;ch=getchar();}
return x*ans;
}
const long long N=40000005;
long long n,a[N],f[N],num[N],sum[N];
int main() {
n=read(); long long type=read();
if(type==0) {
for(register int i=1;i<=n;++i) {
a[i]=read(); sum[i]=sum[i-1]+a[i];
}
}
memset(f,0,sizeof(f)); f[0]=0;
memset(f,0x3f,sizeof(f)); f[0]=0;
int ans=0;
for(register int i=1;i<=n;++i) {
for(register int j=ans;j<i;++j) {
if(num[j]<=sum[i]-sum[j]) {
if(f[j]+(sum[i]-sum[j])*(sum[i]-sum[j])<=f[i]) {
ans=j;
f[i]=f[j]+(sum[i]-sum[j])*(sum[i]-sum[j]);
num[i]=sum[i]-sum[j];
}
}
}
// if(ans<lst) cout<<"Error"<<' '<<ans<<' '<<res<<endl;
// if(a[i]==1) cout<<f[i-1]<<' '<<f[i]<<endl;
}
cout<<f[n]<<endl;
return 0;
}
发题解不易，今天的Rp不易，希望各位看到这里的巨老给本蒟蒻留一个赞
2019.11.17
