动态规划优化(二)

这部分内容介绍了单调队列优化，斜率优化等等

辅助算法，区间最值的ST算法

单调队列优化dp

POJ1821

const int maxn = 16000 + 10;
const int maxm = 100 + 10;

class Node {
public:
    int S, L, P;

    bool operator< (const Node& rhs) const {
        return S < rhs.S;
    }
};

Node A[maxn];
int n, m;

int f[maxm][maxn];

void init() {
    Set(f, 0);
}

inline int g(int i, int k) {
    return f[i - 1][k] - A[i].P * k;
}

void solve() {
    sort(A + 1, A + 1 + m);

    deque<int> que;
    _rep(i, 1, m) {
        // == init queue ==
        for(int k = max(0, A[i].S - A[i].L); k <= A[i].S - 1; k++) {
            while (!que.empty() && g(i, que.back()) <= g(i, k)) que.pop_back();
            que.push_back(k);
        }
        // == init finished ==

        _rep(j, 1, n) {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            if(j >= A[i].S) {
                while (!que.empty() && j - A[i].L > que.front()) que.pop_front();

                if(!que.empty()) f[i][j] = max(f[i][j], A[i].P * j + g(i, que.front()));
            }
        }
    }

    cout << f[m][n] << endl;
}

int main() {
    freopen("input.txt", "r", stdin);
    cin >> n >> m;

    // == input ==
    _rep(i, 1, m) {
        scanf("%d%d%d", &A[i].L, &A[i].P, &A[i].S);
    }
    // == input finished ==

    init();

    solve();
}

单调队列优化+二叉堆

POJ3017

双端队列版本

const int maxn = 100006;
llong A[maxn];
int N;
llong M;

multiset<llong> s;
multiset<llong>::iterator it;

llong f[maxn];

void init() {
    s.clear();
    Set(f, 0);
}

void solve() {
    deque<int> que;
    llong sum = 0;
    int p = 1;

    _rep(i, 1, N) {
        sum += A[i];

        while (sum > M) sum -= A[p++];

        // == get que[front] ==
        while (!que.empty() && que.front() < p) {
            int t = que.front();
            que.pop_front();

            if(!que.empty() && (it = s.find(f[t] + A[que.front()])) != s.end()) {
                s.erase(it);
            }
        }
        // == que[front] finished ==
        // == now que[front] is p  ==

        // == Monotonic queue ==
        while (!que.empty() && A[que.back()] <= A[i]) {
            int b = que.back();
            que.pop_back();

            if(!que.empty() && (it = s.find(f[que.back()] + A[b])) != s.end()) {
                s.erase(it);
            }
        }
        // == Monotonic queue finished ==

        if(!que.empty()) s.insert(f[que.back()] + A[i]);
        que.push_back(i);

        f[i] = f[p - 1] + A[que.front()];
        if(s.begin() != s.end()) f[i] = min(f[i], *s.begin());
    }

    cout << f[N] << endl;
}

int main() {
    freopen("input.txt", "r", stdin);
    cin >> N >> M;

    // == input ==
    _rep(i, 1, N) {
        scanf("%lld", &A[i]);
        if(A[i] > M) {
            puts("-1");
            return 0;
        }
    }
    // == input finished ==

    solve();

}

ST+双端队列

// == ST Algorithm ==
void ST() {
    _rep(i, 1, N) Q[i][0] = A[i];
    int t = log(N) / log(2) + 1;
    _for(k, 1, t) _rep(i, 1, N - (1<<k) + 1) {
            Q[i][k] = max(Q[i][k - 1], Q[i + (1 << (k - 1))][k - 1]);
        }
}

llong ask(int l, int r) {
    int k = log(r - l + 1) / log(2);
    return max(Q[l][k], Q[r - (1<<k) + 1][k]);
}
// == ST Algorithm finished ==

void solve() {
    ST();
    deque<int> que;
    llong sum = 0;
    int p = 1;

    _rep(i, 1, N) {
        sum += A[i];
        while (sum > M) sum -= A[p++];

        // == get que[front] ==
        while (!que.empty() && que.front() < p) {
            int t = que.front();
            que.pop_front();

            if(!que.empty() && (it = s.find(f[t] + A[que.front()])) != s.end()) s.erase(it);
        }
        // == que[front] finished, now que[front] = p

        // == Monotonic queue ==
        while (!que.empty() && A[que.back()] <= A[i]) {
            int b = que.back();
            que.pop_back();

            if(!que.empty() && (it = s.find(f[que.back()] + A[b])) != s.end()) s.erase(it);
        }

        if(!que.empty()) s.insert(f[que.back()] + A[i]);
        que.push_back(i);
        // == Monotonic queue finished ==

        f[i] = f[p - 1] + ask(p, i);
        if(s.begin() != s.end()) f[i] = min(f[i], *s.begin());
    }
    cout << f[N] << endl;
}

单调队列优化多重背包

HDU2191

const int inf = 0xcf;
const int maxn = 20000 + 10;
int n, m;

int f[maxn];
int W[maxn], V[maxn], C[maxn];

void init() {
    Set(f, inf);
    f[0] = 0;
}

inline int g(int i, int u, int k) {
    return f[u + k * V[i]] - k * W[i];
}

void solve() {
    init();

    _rep(i, 1, n) {
        scanf("%d%d%d", &V[i], &W[i], &C[i]);
        _for(u, 0, V[i]) {
            deque<int> que;

            // == status variable p ==
            int maxp = (m - u) / V[i];
            _forDown(k, maxp - 1, max(0, maxp - C[i])) {
                while (!que.empty() && g(i, u, que.back()) <= g(i, u, k)) que.pop_back();
                que.push_back(k);
            }

            _forDown(p, maxp, 0) {
                // == compare que.front and p-1
                while (!que.empty() && que.front() > p - 1) que.pop_front();
                if(!que.empty()) f[u + p * V[i]] = max(f[u + p * V[i]], g(i, u, que.front()) + p * W[i]);

                // == compare que.back and maintain monotonic queue
                if(p - 1 - C[i] >= 0) {
                    int k2 = p - 1 - C[i];
                    while (!que.empty() && g(i, u, que.back()) <= g(i, u, k2)) que.pop_back();
                    que.push_back(k2);
                }
            }
            // == status variable finished ==
        }
    }
    int ans = 0;
    _rep(i, 1, m) ans = max(ans, f[i]);
    cout << ans << endl;
}

int main() {
    freopen("input.txt", "r", stdin);
    int T;
    scanf("%d", &T);

    while (T--) {
        scanf("%d%d", &m, &n);
        solve();
    }
}

斜率优化

POJ1180

const int maxn = 300000 + 10;
llong sumc[maxn], sumt[maxn];
llong f[maxn];

int n, s;

void init() {
    Set(f, 0x3f);
    f[0] = 0;
}

int main() {
    freopen("input.txt", "r", stdin);
    cin >> n >> s;
    init();

    // == get input ==
    _rep(i, 1, n) {
        int t, c;
        scanf("%d%d", &t, &c);
        sumt[i] = sumt[i - 1] + t;
        sumc[i] = sumc[i - 1] + c;
    }
    // == input finished ==

    deque<int> q;
    q.push_back(0);

    _rep(i, 1, n) {
        while (q.size() >= 2 && (f[q[1]] - f[q[0]]) <= (s + sumt[i]) * (sumc[q[1]] - sumc[q[0]]) ) q.pop_front();
        f[i] = f[q[0]] - (s + sumt[i]) * sumc[q[0]] + sumt[i] * sumc[i] + s * sumc[n];
        while (q.size() >= 2 && (f[*(q.end()-1)] - f[*(q.end()-2)]) * (sumc[i] - sumc[*(q.end()-1)]) >= (f[i] - f[*(q.end()-1)]) * (sumc[*(q.end()-1)] - sumc[*(q.end()-2)]) )
            q.pop_back();
        q.push_back(i);
    }
    cout << f[n] << endl;
}

斜率优化+二分或二叉堆

BZOJ2726

const int maxn = 300000 + 10;
llong sumc[maxn], sumt[maxn];
llong f[maxn];
int q[maxn], ql, qr;

int n, s;

void init() {
    Set(f, 0x3f);
    f[0] = 0;
    Set(q, 0);
    ql = qr = 0;
}

int bSearch(const int ql, const int qr, int k) {
    int l = ql, r = qr;
    if(l == r) return q[l];

    while (l < r) {
        int mid = (l + r) >> 1;
        if(f[q[mid + 1]] - f[q[mid]] <= k * (sumc[q[mid + 1]] - sumc[q[mid]]) ) l = mid + 1;
        else r = mid;
    }
    return q[l];
}

int main() {
    freopen("input.txt", "r", stdin);
    cin >> n >> s;
    init();

    // == get input ==
    _rep(i, 1, n) {
        int t, c;
        scanf("%d%d", &t, &c);
        sumt[i] = sumt[i - 1] + t;
        sumc[i] = sumc[i - 1] + c;
    }
    // == input finished ==

    ql = qr = 1;
    q[1] = 0;

    _rep(i, 1, n) {
        int p = bSearch(ql, qr, sumt[i] + s);
        f[i] = f[p] - (s + sumt[i]) * sumc[p] + sumt[i] * sumc[i] + s * sumc[n];
        while (ql < qr && (f[q[qr]] - f[q[qr - 1]]) * (sumc[i] - sumc[q[qr]]) >= (f[i] - f[q[qr]]) * (sumc[q[qr]] - sumc[q[qr - 1]]) )
            qr--;
        q[++qr] = i;
    }
    cout << f[n] << endl;
}

斜率优化任务规划模型

codeforces311B

const int maxn = 100000 + 10;
const int maxm = 100 + 10;
const int inf = 0x3f;
llong f[maxm][maxn], D[maxn], H[maxn], T[maxn], q[maxn];
llong g[maxn];
int N, M, P;
llong A[maxn], S[maxn];

void init() {
    sort(A + 1, A + 1 + M);
    _rep(i, 1, M) {
        S[i] = S[i - 1] + A[i];
    }
    Set(f, inf);
    Set(g, 0);
    Set(q, 0);
    f[0][0] = 0;
}

void solve() {
    _rep(i, 1, P) {
        _rep(k, 1, M) g[k] = f[i - 1][k] + S[k];

        int l = 1, r = 1;
        q[1] = 0;

        _rep(j, 1, M) {
            while (l < r && (g[q[l+1]] - g[q[l]]) <= (A[j] * (q[l+1] - q[l]) ) ) l++;
            f[i][j] = min(f[i - 1][j], g[q[l]] + A[j] * (j - q[l]) - S[j] );

            while (l < r && ( (g[q[r]] - g[q[r-1]]) * (j - q[r]) >= (g[j] - g[q[r]]) * (q[r] - q[r-1]) ) ) r--;
            q[++r] = j;
        }
    }
    cout << f[P][M] << endl;
}

int main() {
    freopen("input.txt", "r", stdin);

    // == input ==
    cin >> N >> M >> P;
    _rep(i, 2, N) {
        int x;
        scanf("%d", &x);
        D[i] = D[i - 1] + x;
    }

    _rep(i, 1, M) {
        int h, t;
        scanf("%d%d", &h, &t);
        A[i] = t - D[h];
    }
    // == input finished ==

    // == init data ==
    init();
    // == init data finished ==

    // == solve the problem ==
    solve();
}