O(n^2)过系列,数据有待加强
查看原帖
O(n^2)过系列,数据有待加强
698657
free_fall楼主2023/7/31 21:17

这条代码居然没有TLE

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e4+5;
int n,l,c[N],f[N],pre[N];
int p(int x){
	return x*x;
}
signed main(){
	scanf("%lld%lld",&n,&l);
	l++;
	for(int i=1;i<=n;i++){
		scanf("%lld",&c[i]);
		c[i]=c[i]+1+c[i-1];
	}
	memset(f,0x3f,sizeof f);
	f[0]=0;
	for(int i=1;i<=n;i++){
		for(int j=pre[i-1];j<=i;j++){
			if(f[i]>=f[j-1]+p(c[i]-c[j-1]-l)){
				f[i]=f[j-1]+p(c[i]-c[j-1]-l);
				pre[i]=j;
			}
		}
	}
	printf("%lld",f[n]);
	return 0;
}
2023/7/31 21:17
加载中...