本文共 2032 字，大约阅读时间需要 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/