关于特殊情况的处理
查看原帖
关于特殊情况的处理
372708
Yahbim楼主2021/7/7 21:44

各位dalao,请问在队列中没有一个点,满足它到它下一个点的斜率大于当前的斜率时(即 size==0size==0 时),应当取哪一个点?我采用了deque实现,这样的话,当 size==0size==0 ,返回的是 00 ,直接WA;但单纯的添加出队条件 size()>1size()>1 ,又会导致 size()size() 变大了 11 ,还是WA;如果原因确实是我说的这样,求各位dalao给出一个解决方案,qwq

CODE:

#include<bits/stdc++.h>
#define f(i) (s[(i)]+(i))
#define g(i) (f(i)+1+l)
#define sqr(i) ((i)*(i))
#define h(i) (dp[i]+sqr(g(i)))
#define slope(i,j) (long double)((h(i)-h(j))/(g(i)-g(j)))
using namespace std;
typedef long long ll;
const int N=(int)5e4+5;

int n,l,c[N];
ll s[N],dp[N];
deque<int> q;

int main(){
	scanf("%d%d",&n,&l);
	for(int i=1;i<=n;i++)
		scanf("%d",&c[i]);
	for(int i=1;i<=n;i++)
		s[i]=s[i-1]+c[i];
	q.push_front(0);
	for(int i=1;i<=n;i++){
		long double k=2*f(i);
		while(q.size()>1 && slope(q.front(),q.front()+1)<=k) q.pop_front();
		int j=q.front();
		dp[i]=dp[j]+sqr(f(i)-g(j));
		while(!q.empty() && slope(q.back()-1,i)<=slope(q.back()-1,q.back())) q.pop_back();
		q.push_back(i);
	}
	printf("%lld",dp[n]);
	return 0;
}
2021/7/7 21:44
加载中...