rt，最近的几道斜率优化题属实是不会了

这道题

写斜率函数 $\text{getslope}$ ,返回 $\text{double}$大概是因为精度问题只有35分，而展开成乘的形式就过了

$\text{getslope}$版：

#include <bits/stdc++.h>
using namespace std;
namespace DCM{
   #define int long long
   const int maxn=5e6+10;
   int n,dp[maxn],t[maxn],f[maxn],sumt[maxn],sumf[maxn],s,q[maxn];
   long double getslope(int j,int k) {
       return (long double)1.*(dp[j]-dp[k])/(1.*(sumf[j]-sumf[k]));
   }
   void output() {
   	for(int i=1;i<=n;i++) {
   		cout<<dp[i]<<' ';
   	}
   	cout<<"\n";
   	for(int i=1;i<=n;i++) {
   		cout<<sumt[i]<<' '<<sumf[i]<<'\n';
   	}
   	cout<<'\n';
   }
   void work() {
       cin>>n>>s;
       for(int i=1;i<=n;i++) {
           cin>>t[i]>>f[i];
           sumt[i]=sumt[i-1]+t[i];
           sumf[i]=sumf[i-1]+f[i];
       }
       
       int tail=1;
       for(int i=1;i<=n;i++) {
           int ans;
           if(tail>1) {
               int l=1,r=tail;
               while(l<=r) {
                   int mid=(l+r)/2;
                   if(getslope(q[mid+1],q[mid])<(long double)(s+sumt[i])) l=mid+1;
                   //if(dp[q[mid+1]]-dp[q[mid]]<(sumt[i]+s)*(sumf[q[mid+1]]-sumf[q[mid]])) l=mid+1;
                   else r=mid-1,ans=mid;
               }
           }
           else ans=1;
           int j=q[ans];
           dp[i]=dp[j]+sumt[i]*(sumf[i]-sumf[j])+s*(sumf[n]-sumf[j]);
// 			cout<<ans<<'\n';
// 			output();
           while(tail>1&&getslope(i,q[tail])<=getslope(q[tail],q[tail-1]))
               tail--;
           q[++tail]=i;
       }
       cout<<dp[n];
   }
   #undef int
}
int main() {
   return DCM::work(),0;
}

乘的形式版：

#include <bits/stdc++.h>
using namespace std;
namespace DCM{
	#define int long long
    const int maxn=5e6+10;
    int n,dp[maxn],t[maxn],f[maxn],sumt[maxn],sumf[maxn],s,q[maxn];
    long double getslope(int j,int k) {
        return (long double)1.*(dp[j]-dp[k])/(1.*(sumf[j]-sumf[k]));
    }
    void output() {
    	for(int i=1;i<=n;i++) {
    		cout<<dp[i]<<' ';
		}
		cout<<"\n";
		for(int i=1;i<=n;i++) {
			cout<<sumt[i]<<' '<<sumf[i]<<'\n';
		}
		cout<<'\n';
	}
    void work() {
        cin>>n>>s;
        for(int i=1;i<=n;i++) {
            cin>>t[i]>>f[i];
            sumt[i]=sumt[i-1]+t[i];
            sumf[i]=sumf[i-1]+f[i];
        }
        
        int tail=1;
        for(int i=1;i<=n;i++) {
            int ans;
            if(tail>1) {
                int l=1,r=tail;
                while(l<=r) {
                    int mid=(l+r)/2;
                    //if(getslope(q[mid+1],q[mid])<(long double)(s+sumt[i])) l=mid+1;
                    if(dp[q[mid+1]]-dp[q[mid]]<(sumt[i]+s)*(sumf[q[mid+1]]-sumf[q[mid]])) l=mid+1;
                    else r=mid-1,ans=mid;
                }
            }
            else ans=1;
            int j=q[ans];
            dp[i]=dp[j]+sumt[i]*(sumf[i]-sumf[j])+s*(sumf[n]-sumf[j]);
//			cout<<ans<<'\n';
//			output();
            while(tail>1&&(dp[q[tail]]-dp[q[tail-1]])*(sumf[i]-sumf[q[tail]])>=(dp[i]-dp[q[tail]])*(sumf[q[tail]]-sumf[q[tail-1]]))
                tail--;
            q[++tail]=i;
        }
        cout<<dp[n];
    }
    #undef int
}
int main() {
    return DCM::work(),0;
}

而对于这道题

写乘的形式就会得到0的成绩，写成斜率函数就过了。

两种写法：

double slope(int i,int j) {
		return 1.0*(dp[i]-dp[j])/(a[j+1].w-a[i+1].w);
	}
//--------
for(int i=1;i<=cnt;i++) {
            while((head<tail)&&slope(q[head],q[head+1])<=a[i].l)
                head++;
            int j=q[head];
            dp[i]=dp[j]+1ll*a[j+1].w*a[i].l;
            while(head<tail&&slope(q[tail-1],q[tail])>=slope(q[tail],i))
                --tail;
            q[++tail]=i;
        }

for(int i=1;i<=cnt;i++) {
            while((head<tail)&&(dp[q[head]]-dp[q[head+1]])<=a[i].l*(a[q[head+1]+1].w-a[q[head]+1].w))
                head++;
            int j=q[head];
            dp[i]=dp[j]+a[j+1].w*a[i].l;
            
            while(head<tail&&(dp[q[tail-1]]-dp[q[tail]])*(a[i+1].w-a[q[tail]+1].w)>=(dp[q[tail]]-dp[i])*(a[q[tail]+1].w-a[q[tail-1]+1].w))
                tail--;
            q[++tail]=i;
        }

萌新求助：斜率优化到底啥时候写哪种写法啊？