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