关于斜率dp(非调题+玄关)
查看原帖
关于斜率dp(非调题+玄关)
556545
_anll_楼主2024/9/26 15:15

rt,今天复习斜率dp,突然发现之前过的一道题,有一些不太理解的地方,所以想发个帖子问问各位神犇orz。

这一份代码是可以通过的:

#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int M=4001005;
int n,s,ans=1e18,maxn,q[M],p[M],dp[M],que[M];
long double sl(int i,int j){
	return 1.0*((dp[i]+q[i])-(dp[j]+q[j]))/(p[i]==p[j]?1e-9:p[i]-p[j]);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>s;int awa;
	for(int i=1;i<=n;i++){
		cin>>awa;maxn=max(maxn,awa);
		p[awa]+=1,q[awa]+=awa;
	}
	for(int i=1;i<=maxn+s;i++) p[i]+=p[i-1],q[i]+=q[i-1];
	int l=1,r=0;
	for(int i=0;i<=maxn+s;i++){
		if(i-s>=0){
			while(l<r&&sl(que[r],que[r-1])>sl(i-s,que[r])) r-=1;
			que[++r]=i-s;
		}
		while(l<r&&sl(que[l+1],que[l])<i) l+=1;
		int j=que[l];
		if(i<s) dp[i]=p[i]*i-q[i];
		else dp[i]=dp[j]+(p[i]-p[j])*i-q[i]+q[j];
		if(i>=maxn) ans=min(ans,dp[i]);
	}
	cout<<ans;
	return 0;
}

这一份是通过不了的:

#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int M=4001005;
int n,s,ans=1e18,maxn,q[M],p[M],dp[M],que[M];
long double sl(int i,int j){
	return 1.0*((dp[i]+q[i])-(dp[j]+q[j]))/(p[i]==p[j]?1e-9:p[i]-p[j]);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>s;int awa;
	for(int i=1;i<=n;i++){
		cin>>awa;maxn=max(maxn,awa);
		p[awa]+=1,q[awa]+=awa;
	}
	for(int i=1;i<=maxn+s;i++) p[i]+=p[i-1],q[i]+=q[i-1];
	int l=1,r=0;
	for(int i=0;i<=maxn+s;i++){
		if(i-s>=0){
			while(l<r&&sl(que[r-1],que[r])>sl(que[r],i-s)) r-=1;
			que[++r]=i-s;
		}
		while(l<r&&sl(que[l],que[l+1])<i) l+=1;
		int j=que[l];
		if(i<s) dp[i]=p[i]*i-q[i];
		else dp[i]=dp[j]+(p[i]-p[j])*i-q[i]+q[j];
		if(i>=maxn) ans=min(ans,dp[i]);
	}
	cout<<ans;
	return 0;
}

但其实只是对于 sl()sl() 这个函数中代入参数的顺序进行了交换,但因为本人太菜了无法理解为什么交换顺序会导致结果从 100pts -> 10pts,希望有大佬可以解答orz。

2024/9/26 15:15
加载中...