分析：

f[i]表示前i个分组后的最小费用

f[i]=min(f[j]+t[i](c[i]-c[j])+s(c[n]-c[j]));

前j个 i~j的答案因为分了一组，所以在此之后的组肯定至少有一个等待的s

c是费用前缀和数组

t是时间

直接把min甩掉

\[f[i]=f[j]+t[i]*(c[i]-c[j])+s*(c[n]-c[j])\]

\[f[j]=f[i]-t[i]*(c[i]-c[j])-s*(c[n]-c[j])\]

\[f[j]=f[i]-t[i]*c[i]+t[i]*c[j]-s*c[n]+s*c[j]\]

\(f[j]=(s+t[i])*c[j]+f[i]-t[i]*c[i]-s*c[n]\)
y = k * x + b

因为j已知，所以一次函数中的y和x都要是j为下标的

因此推出上述式子

发现我们要求的是f[i]最小

那么就是b最小

(c[j],f[j])

然后直线过每个点找最小的截距

上凸放弃凸点

下凸可能是凸点

相邻的斜率单调递增的

所以最有解的点左斜率小于k右斜率大于k

单调队列，所以只要考虑右斜率

code:

 #include<cstdio> #include<deque> using namespace std; deque<long long>q; long long t[5005],f[5005]; long long h[5005]; long long dp[5005];//dp[i]表示在i分组完毕后的答案 int main() { freopen("batch.in","r",stdin); freopen("batch.out","w",stdout); long long n,s; scanf("%lld%lld",&n,&s); for(long long i=1;i<=n;i++) { scanf("%lld%lld",&t[i],&f[i]); t[i]+=t[i-1];//计算时间前缀和 } for(long long i=n;i>=1;i--) { h[i]=h[i+1]+f[i];//费用后缀，逆推准备 } q.push_back(n+1);//初始化，此双端队列基本保证单调 for(long long i=n;i>=1;i--)//倒推 { //保证队列中至少有两个数，且(q[0],q[1])的组合结果比元两者组合的答案大 while(q.size()&&q.size()!=1&&h[i]*(t[q[0]-1]-t[q[1]-1])>=dp[q[1]]-dp[q[0]]) { q.pop_front();//就把q[0]弹出去，因为Q【0】在这个组合中会拖后腿 } //将i加入i~q[0]和q[0]至n dp[i]=dp[q[0]]+h[i]*(s+t[q[0]-1]-t[i-1]); while(q.size()&&q.size()!=1) { long long len=q.size(); //(i,len-1)和（len-1,len-2)比较 if((dp[i]-dp[q[len-1]])*(t[q[len-2]-1]-t[q[len-1]-1])<=(dp[q[len-1]]-dp[q[len-2]])*(t[q[len-1]-1]-t[i-1])) {//算斜率是哪凸 q.pop_back(); } else { break; } } q.push_back(i); } printf("%lld\n",dp[1]); return 0; }

任务安排

分析：

code: