初学斜率优化dp萌新求条
查看原帖
初学斜率优化dp萌新求条
788434
封禁用户楼主2024/7/20 09:52

rt,我的代码哪错了,玄关

#include<bits/stdc++.h>
using namespace std;
long long n,a[1000001],s[1000001],dp[1000001],l ,ans; 
#define x(i) (s[i])

#define y(i) (dp[i]+s[i]*s[i])

#define k(i) (2*(s[i]-l))

double slope(int i,int j){
	return (double)(y(j)-y(i))/(x(j)-x(i));
}
int main(){
	cin>>n>>l;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		s[i]=s[i-1]+a[i];
	}
	deque<int>dq={0};
	for(int i=1;i<=n;i++){
		while(dq.size()>1&&slope(dq[0],dq[1])<k(i))dq.pop_front();
		int j=dq.front();
		dp[i]=dp[j]+(s[i]-s[j]-l)*(s[i]-s[j]-l);
		while(dq.size()>1&&slope(dq[dq.size()-2],dq.back())>slope(dq.back(),i))dq.pop_back();
		dq.push_back(i);
	}
	cout<<dp[n]-1<<'\n';
	return 0;
}#include<bits/stdc++.h>
using namespace std;
long long n,a[1000001],s[1000001],dp[1000001],l ,ans; 
#define x(i) (s[i])
#define y(i) (dp[i]+s[i]*s[i])
#define k(i) (2*(s[i]-l))
double slope(int i,int j){
	return (double)(y(j)-y(i))/(x(j)-x(i));
}
int main(){
	cin>>n>>l;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		s[i]=s[i-1]+a[i];
	}
	deque<int>dq={0};
	for(int i=1;i<=n;i++){
		while(dq.size()>1&&slope(dq[0],dq[1])<k(i))dq.pop_front();
		int j=dq.front();
		dp[i]=dp[j]+(s[i]-s[j]-l)*(s[i]-s[j]-l);
		while(dq.size()>1&&slope(dq[dq.size()-2],dq.back())>slope(dq.back(),i))dq.pop_back();
		dq.push_back(i);
	}
	cout<<dp[n]-1<<'\n';
	return 0;
}
2024/7/20 09:52
加载中...