请求加强数据

RT，讨论区一堆暴力过的暂且不谈，甚至直接每次从前500项转移都能过，代码如下：

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=50005;
int n,l,a[N];
long long sum[N],f[N];
signed main(){
	scanf("%d%d",&n,&l),++l;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),sum[i]=sum[i-1]+(++a[i]);
	for(int i=1;i<=n;i++){
		f[i]=LLONG_MAX;
	    for(int j=max(0,i-500);j<i;j++)
			f[i]=min(f[i],f[j]+(sum[i]-sum[j]-l)*(sum[i]-sum[j]-l));
	}
	printf("%lld",f[n]);
	return 0;
}

~~本来想找P4360，P3195这两道斜率优化的题练手的，结果在写暴力检验自己推出的式子的正确性时发现就这么过了搞得写正解的兴趣都没有了~~

讨论操作

回复

相关推荐

请求加强数据