社区讨论
为什么不会RE
P2120[ZJOI2007] 仓库建设参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @lo9n8g0g
- 此快照首次捕获于
- 2023/10/28 14:10 2 年前
- 此快照最后确认于
- 2023/10/28 14:10 2 年前
加上这句就 A 了,没加这句是 WA 不是 RE,为什么?
CPPdouble Slope(int i, int j) {
if (x(i) == x(j)) return INF;//加了这句就A了,防止除数是0
return (y(i) - y(j)) / ((x(i) - x(j)) * 1.0);
}
CPP#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int nn = 1e6 + 10;
typedef long long LL;
const LL INF = 1e16;
int N;
LL F[nn], SumP[nn], SumT[nn];
LL X[nn], P[nn], C[nn];
int L, R, Q[nn];
LL x(int i) { return SumP[i]; }
LL y(int i) { return F[i] + SumT[i]; }
double Slope(int i, int j) {
if (x(i) == x(j)) return INF;//加了这句就A了
return (y(i) - y(j)) / ((x(i) - x(j)) * 1.0);
}
int main () {
ios::sync_with_stdio(0);
cin >> N;
for (int i = 1; i <= N; i ++) cin >> X[i] >> P[i] >> C[i];
for (int i = 1; i <= N; i ++) {
SumP[i] = SumP[i - 1] + P[i];
SumT[i] = SumT[i - 1] + P[i] * X[i];
}
L = R = 1;
for (int i = 1; i <= N; i ++) {
while (L < R && Slope(Q[L], Q[L + 1]) <= X[i]) L++;
F[i] = F[Q[L]] + X[i] * (SumP[i] - SumP[Q[L]]) - (SumT[i] - SumT[Q[L]]) + C[i];
while (L < R && Slope(Q[R - 1], Q[R]) >= Slope(Q[R], i)) R--;
Q[++R] = i;
}
LL Ans = F[N];
for (int i = N; i >= 1; i --) {
Ans = min (Ans, F[i]);
if (P[i]) break;
}
cout << Ans;
}
/*
Val[j~i]=Sum[N]-Sum[j-1]-TOT[j~i]*X[i]
*/
回复
共 1 条回复,欢迎继续交流。
正在加载回复...