本文共 1978 字，大约阅读时间需要 6 分钟。
为了解决这个问题，我们需要找到每一关植物攻击力的最小总和。我们可以通过数学建模和单调栈的方法来高效解决这个问题。
#include#include #include #include #include using namespace std;struct pt { double x, y;};double slope(const pt &u, const pt &v) { return (v.y - u.y) / (v.x - u.x);}double main() { int n, D; scanf("%d %d", &n, &D); double *s = new double[n + 1]; for (int i = 1; i <= n; ++i) { double A, X; scanf("%lf %lf", &A, &X); s[i] = s[i - 1] + A; } pt *sta = new pt[2 * n]; int top = 0; for (int T = 1; T <= n; ++T) { double A, X; scanf("%lf %lf", &A, &X); sta[top].x = D * T; sta[top].y = s[T - 1]; while (top > 0 && slope(sta[top - 1], sta[top]) >= slope(sta[top], sta[top + 1])) { top--; } sta[top + 1].x = X + D * T; sta[top + 1].y = s[T]; int l = 1, r = top; while (r - l > 3) { int mid = (l + r) / 2; int mmid = mid + 1; if (slope(sta[mid], sta[top + 1]) > slope(sta[mmid], sta[top + 1])) { l = mid; } else { r = mmid - 1; } } int op = l; for (int i = l + 1; i <= r; ++i) { if (slope(sta[i], sta[top + 1]) > slope(sta[op], sta[top + 1])) { op = i; } } if (op != l) { ans += slope(sta[op], sta[top + 1]); } else { ans += 0; } } printf("%.0lf\n", round(ans)); delete[] sta; delete[] s; return 0;}
这种方法通过数学建模和单调栈优化，有效地将问题复杂度降低，确保了在较大数据量下的高效计算。
转载地址：http://tsmu.baihongyu.com/