悬关求调斜率优化模板 93pts WA #11

rt，实在没看出来问题，求大佬帮看看，十分感谢！

状态表示：

f_{i,j}

为在

i

处建立第

j

个锯木厂的费用，答案为

f_{n+1,3}

；

状态转移：

f_{i,j}=\min\limits_{k<i} f_{k,j-1}+(w_i-w_k)d_i-x_i+x_k

，其中

d

为原

d

的前缀和，

x

为

wd

的前缀和（

w

为原

w

），

w

为原

w

的前缀和。

CPP

#include <iostream>
#include <queue>
#define front q.front()
#define back q.back()
#define sfront *(q.begin() + 1)
#define sback *(q.rbegin() + 1)
#define int long long

using namespace std;

const int N = 2e4 + 5;

int n, w[N], d[N], x[N], f[N][5];
deque<int> q;

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> w[i] >> d[i + 1];
    for (int i = 1; i <= n + 1; i++)
        d[i] += d[i - 1], x[i] = x[i - 1] + w[i] * d[i], w[i] += w[i - 1], f[i][1] = w[i] * d[i] - x[i];
    for (int k = 2; k <= 3; k++)
    {
        q.push_back(k - 1);
        for (int i = k; i <= n + 1; i++)
        {
            while (q.size() > 1 &&
                   f[sfront][k - 1] + x[sfront] - f[front][k - 1] - x[front] <= (w[sfront] - w[front]) * d[i])
                q.pop_front();
            f[i][k] = f[front][k - 1] + (w[i] - w[front]) * d[i] - x[i] + x[front];
            while (q.size() > 1 && (f[i][k - 1] + x[i] - f[back][k - 1] - x[back]) * (w[back] - w[sback]) <=
                                       (f[back][k - 1] + x[back] - f[sback][k - 1] - x[sback]) * (w[i] - w[back]))
                q.pop_back();
            q.push_back(i);
        }
    }
    cout << f[n + 1][3] << "\n";
    return 0;
}

悬关求调斜率优化模板 93pts WA #11

讨论操作

回复

相关推荐

悬关求调斜率优化模板 93pts WA #11