5 August

P1016 旅行家的预算

单调队列。

再看看单调队列怎么用的。

#include <cstdio>int n, l, r;
double D, dd, d[9], C, p[9], ans;struct node{
double t, x;
} q[999];int main() {
scanf("%lf%lf%lf%lf%d", &D, &C, &dd, &p[0], &n); d[0]=0;
for (int i=1; i<=n; ++i) {
scanf("%lf%lf", &d[i], &p[i]);
if (d[i]-d[i-1]>C*dd) {printf("No Solution\n"); return 0; }
}
d[n+1]=D; double now=0.0;
q[++r]=(node){p[0], now=C}, ans+=p[0]*C;
for (int i=1; i<=n+1; ++i) {
double cos=(d[i]-d[i-1])/dd;
while (l<=r && cos>0) {
if (q[l].x>cos) {now-=cos, q[l].x-=cos; break; }
now-=q[l].x, cos-=q[l].x; ++l;
}
if (i==n+1) {
while (l<=r) ans-=q[l].t * q[l].x, ++l; break;
}
while (l<=r && q[r].t>p[i]) {
ans-=q[r].t*q[r].x, now-=q[r].x; --r;
}
ans+=(C-now)*p[i];
q[++r]=(node){p[i], C-now}; now=C;
}
printf("%.2lf\n", ans);
return 0;
}