jzoj 6305. 最小值

痛定思痛。 2021-10-30 07:08 226阅读 0赞

# Description #

详见OJ

# Solution #

第一眼看上去好像斜率\\(DP\\)，但仔细一看发现不能用单调队列维护。  
然后\\(GG\\)。  
正解使用单调栈来维护。  
我们发现，我们维护的单调栈\\(g\[\]\\)的\\(a\[\]\\)是呈单调不下降的。  
对于新加入的点i，我们需要将单调栈中\\(a\[\]\\)大于\\(a\[i\]\\)的弹出栈中，  
因为这些点的答案需要重新计算。  
对于弹出的\\(f\[g\[\]\]\\)我们与\\(f\[i-1\]\\)取\\(max\\)，然后更新答案，并将点\\(i\\)加入栈中。

# Code #

#include <cstdio>
    #define N 200010
    #define ll long long
    #define mem(x, a) memset(x, a, sizeof x)
    #define fo(x, a, b) for (int x = a; x <= b; x++)
    #define fd(x, a, b) for (int x = a; x >= b; x--)
    using namespace std;
    const int inf = 2147483647;
    int n, a[N], g[N], len = 0;
    ll A, B, C, D, f[N], ma[N], t;
    
    inline int read()
    {
        int x = 0, f = 0; char c = getchar();
        while (c < '0' || c > '9') f = (c == '-') ? 1 : f, c = getchar();
        while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
        return f ? -x : x;
    }
    
    ll solve(int x) {return A * x * x * x + B * x * x + C * x + D;}
    
    ll max(ll x, ll y) {return x > y ? x : y;}
    
    int main()
    {
        freopen("min.in", "r", stdin);
        freopen("min.out", "w", stdout);
        n = read(), A = read(), B = read(), C = read(), D = read();
        fo(i, 1, n) a[i] = read();
        fo(i, 1, n)
        {
            t = f[i - 1];
            while (len && a[g[len]] >= a[i]) t = ma[len] > t ? ma[len] : t, len--;
            g[++len] = i, ma[len] = t;
            f[i] = t + solve(a[i]);
            if (len > 1 && f[g[len - 1]] > f[i]) f[i] = f[g[len - 1]];
        }
        printf("%lld\n", f[n]);
        return 0;
    }

转载于:https://www.cnblogs.com/jz929/p/11369282.html