斜率优化全wa求调
查看原帖
斜率优化全wa求调
985320
TJB_LHY楼主2025/7/20 16:55
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,s;
ll t[5005],f[5005],dp[5005];
struct node{
    ll k,b,i;
};
double cross(node x,node y){
    return (y.b-x.b)*1.0/(x.k==y.k?1e-9:x.k-y.k);
}
deque<node>q;
int main(){
	cin>>n>>s;
	for(int i=1;i<=n;i++){
		cin>>t[i]>>f[i];
        t[i]+=t[i-1];
        f[i]+=f[i-1];
	}
    memset(dp,0x3f,sizeof dp);
    dp[1]=(t[1]+s)*f[1];
    for(int i=2;i<=n;i++){
        while(q.size()>=2 && cross(q[q.size()-1],(node){s+t[i-1],dp[i-1]+s*t[n]-t[i]*f[i],i-1})<=cross(q[q.size()-2],q[q.size()-1]))q.pop_back();
        q.push_back({s+t[i-1],dp[i-1]+s*t[n]-t[i-1]*f[i-1],i-1});
        while(q.size()>=2 && cross(q[0],q[1])<=t[i]+s)q.pop_front();
        dp[i]=q[0].b+q[0].k*f[i];
//     y =    k    *   x    +     b
// dp[j] = (s+t[i])*  f[j]  +  (dp[i]-s*t[n]-t[i]*f[i])
    }
    cout<<dp[n];
	return 0;
}
2025/7/20 16:55
加载中...