社区讨论

一位烧杯想要求助斜率优化

HHaber
P4360[CEOI 2004] 锯木厂选址参与者 4已保存回复 7

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
7 条
当前快照
1 份
快照标识符
@lo8ikwjn
此快照首次捕获于
2023/10/27 19:12
2 年前
此快照最后确认于
2023/10/27 19:12
2 年前
查看原帖
窝推这个逝子不知道对不对：
当 weight[k]×dis[k]−weight[j]×dis[j]weight[k]−weight[j]>dis[i]\frac{weight[k]\times dis[k]-weight[j]\times dis[j]}{weight[k]-weight[j]}>dis[i]
时，选择从 jj 转移。但是和题解的长得很像。
朴素转移逝也和题解对了，没锅。
唯一的差别就是我用的 dis[i]dis[i] 表示的时距离的前缀和，题解使用的是后缀和。
代码通过了样例，然后喜提 58pts.
经检验，并非精度，没开 long long 的问题。
不知道哪里出锅了。也许是逝子？
丑陋的代码：希望有路过的大佬或者划水的帮忙调一下。
CPP
#include<bits/stdc++.h>
using namespace std;
int n,ans=2e9;
const int N=2e4+4;
int f[N];
int tot;
int dis[N],weight[N];
int head=1,tail=1;
int q[N],d[N],w[N];
int sq(int i){
  return weight[i]*dis[i];
}
int main(){
 cin>>n;
 for(int i=1;i<=n;i++){
  cin>>w[i]>>d[i];
  dis[i+1]=dis[i]+d[i];	//Before i this point.
  weight[i]=weight[i-1]+w[i];
 }
 for(int i=1;i<=n+1;i++) tot+=(dis[n+1]-dis[i])*w[i];
 for(int i=1;i<=n;i++){
  while(head<tail&&sq(q[head+1])-sq(q[head])<dis[i]*(weight[q[head+1]]-weight[q[head]])) head++;
  f[i]=tot-weight[q[head]]*(dis[n+1]-dis[q[head]])-(weight[i]-weight[q[head]])*(dis[n+1]-dis[i]);
  while(head<tail&&(sq(i)-sq(q[tail]))*(weight[q[tail]]-weight[q[tail-1]])<(sq(q[tail])-sq(q[tail-1])*(weight[i]-weight[q[tail]]))) tail--;
  q[++tail]=i;
 }
 for(int i=1;i<=n;i++) ans=min(ans,f[i]);
 cout<<ans<<endl;
 return 0;
}

回复

共 7 条回复，欢迎继续交流。

正在加载回复...