2010-1100

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

设dp[n][k]表示将前n个小朋友分到前k个班中，易写出状态转移方程：

dp[n][k] = min {dp[i][k - 1] + gk * (sum[n] - sum[i]) | A <= n - i <= B}

sum[n] = sigma {(xi - L)^2^ | i <= n}

但现在的状态数为10000 × 200，转移复杂度为O(n)，显然会TLE

将转移方程整理一下：

dp[n][k] = gk * sum[n] + min {dp[i][k - 1] - gk * sum[i] | n - B <= i <= n - A}

固定k时，当n增大，方程的形式不变，只是可选范围改变

对于n转移到n+1时，i=n-B的状态不可再选，而i=n-A的状态应该加入可选范围内

故可维护一个单调递增队列，每次转移之前将新的可选状态从队列尾插入，且把比其大的都pop出，同时保证队列头的元素在可选范围之内。

这样每次转移就可以只取队列头的元素，将转移复杂度降为O(1)。

总的时间复杂度为O(n*k)，空间复杂度为O(n)。

{{{
#!cpp
#include <cstdio>
#include <cstring>
#include <cassert>
#include <algorithm>
using namespace std;

typedef long long LL;
typedef pair<LL, int> PII;

const LL INF = 223372036854775807LL;
const int MAXN = 10010;
const int MAXK = 210;

class Queue {
public:
    PII v[MAXN];
    int open, closed;
    void init() {
        open = closed = 0;   
    }
    bool empty() {
        return closed <= open;   
    }
    void push(PII now) {
        v[closed++] = now;   
    }
    void pop_back() {
        closed--;   
    }
    void pop_front() {
        open++;   
    }
    PII back() {
        return v[closed - 1];   
    }
    PII front() {
        return v[open];   
    }
}Q;

LL f[MAXN][2];
LL s[MAXN], s2[MAXN], P[MAXN], x[MAXN], g[MAXK];

inline void insert(int t, int pos, int k) {
    if (f[pos][t] == INF) return;
    LL fv = f[pos][t] - g[k] * P[pos];
    while (!Q.empty() && Q.back().first >= fv) {
        Q.pop_back();   
    }
    Q.push(make_pair(fv, pos));
}

inline LL get(int atleast, int &ret) {
    while (!Q.empty() && Q.front().second < atleast) {
        Q.pop_front();   
    }  
    ret = -1; 
    if (Q.empty()) return INF;
    ret = Q.front().second;
    return Q.front().first;
}

int main() {

    int N, K, A, B;
    while (scanf("%d %d %d %d", &N, &K, &A, &B) != EOF) {
        assert(1 <= N && N <= 10000);
        assert(1 <= K && K <= 200);
        assert(1 <= A && A <= B && B <= N);
        LL L = 0;
        for (int i = 1; i <= N; i++) {
            scanf("%lld", &x[i]);
            assert(1 <= x[i] && x[i] <= 100000);
            L += x[i];
        }        
        L /= N;
        P[0] = 0;
        for (int i = 1; i <= N; i++) {
            P[i] = P[i - 1] + (x[i] - L) * (x[i] - L);
        }
        for (int i = 1; i <= K; i++) {
            scanf("%lld", &g[i]);
            assert(-1000 <= g[i] && g[i] <= 1000);
        }
        int t0 = 0, t1;

        // k = 0
        f[0][t0] = 0LL; 
        for (int i = 1; i <= N; i++) {
            f[i][t0] = INF;
        }

        LL ans = INF;
        int ansk, ansopt, opt;
        for (int k = 1; k <= K; k++) {
            t1 = 1 - t0;   
            Q.init();
            for (int n = 0; n <= N; n++) {
                if (n < k * A || n > k * B) {
                    f[n][t1] = INF;
                    continue;
                }
                insert(t0, n - A, k);
                f[n][t1] = g[k] * P[n] + get(n - B, opt);
                if (opt == -1) f[n][t1] = INF;
                if (n == N) { 
                    if (f[n][t1] < ans) {
                        ans = f[n][t1];
                        ansk = k;   
                        ansopt = N - opt;                        
                    }
                }
            }
            t0 = t1;
        }
        if (ans == INF) {
            puts("No solution.");
        }
        else {
            printf("%lld %d %d\n", ans, ansk, ansopt);
        }
    }
    return 0;    
}
}}}

设dp[n][k]表示将前n个小朋友分到前k个班中，易写出状态转移方程：

dp[n][k] = min {dp[i][k - 1] + gk * (sum[n] - sum[i]) | A <= n - i <= B}

sum[n] = sigma {(xi - L)² | i <= n}

但现在的状态数为10000 × 200，转移复杂度为O(n)，显然会TLE

将转移方程整理一下：

dp[n][k] = gk * sum[n] + min {dp[i][k - 1] - gk * sum[i] | n - B <= i <= n - A}

固定k时，当n增大，方程的形式不变，只是可选范围改变

对于n转移到n+1时，i=n-B的状态不可再选，而i=n-A的状态应该加入可选范围内

故可维护一个单调递增队列，每次转移之前将新的可选状态从队列尾插入，且把比其大的都pop出，同时保证队列头的元素在可选范围之内。

这样每次转移就可以只取队列头的元素，将转移复杂度降为O(1)。

总的时间复杂度为O(n*k)，空间复杂度为O(n)。

#include <cstdio>
#include <cstring>
#include <cassert>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef pair<LL, int> PII;
const LL INF = 223372036854775807LL;
const int MAXN = 10010;
const int MAXK = 210;
class Queue {
public:
    PII v[MAXN];
    int open, closed;
    void init() {
        open = closed = 0;   
    }
    bool empty() {
        return closed <= open;   
    }
    void push(PII now) {
        v[closed++] = now;   
    }
    void pop_back() {
        closed--;   
    }
    void pop_front() {
        open++;   
    }
    PII back() {
        return v[closed - 1];   
    }
    PII front() {
        return v[open];   
    }
}Q;
LL f[MAXN][2];
LL s[MAXN], s2[MAXN], P[MAXN], x[MAXN], g[MAXK];
inline void insert(int t, int pos, int k) {
    if (f[pos][t] == INF) return;
    LL fv = f[pos][t] - g[k] * P[pos];
    while (!Q.empty() && Q.back().first >= fv) {
        Q.pop_back();   
    }
    Q.push(make_pair(fv, pos));
}
inline LL get(int atleast, int &ret) {
    while (!Q.empty() && Q.front().second < atleast) {
        Q.pop_front();   
    }  
    ret = -1; 
    if (Q.empty()) return INF;
    ret = Q.front().second;
    return Q.front().first;
}
int main() {
    int N, K, A, B;
    while (scanf("%d %d %d %d", &N, &K, &A, &B) != EOF) {
        assert(1 <= N && N <= 10000);
        assert(1 <= K && K <= 200);
        assert(1 <= A && A <= B && B <= N);
        LL L = 0;
        for (int i = 1; i <= N; i++) {
            scanf("%lld", &x[i]);
            assert(1 <= x[i] && x[i] <= 100000);
            L += x[i];
        }        
        L /= N;
        P[0] = 0;
        for (int i = 1; i <= N; i++) {
            P[i] = P[i - 1] + (x[i] - L) * (x[i] - L);
        }
        for (int i = 1; i <= K; i++) {
            scanf("%lld", &g[i]);
            assert(-1000 <= g[i] && g[i] <= 1000);
        }
        int t0 = 0, t1;
        // k = 0
        f[0][t0] = 0LL; 
        for (int i = 1; i <= N; i++) {
            f[i][t0] = INF;
        }
        LL ans = INF;
        int ansk, ansopt, opt;
        for (int k = 1; k <= K; k++) {
            t1 = 1 - t0;   
            Q.init();
            for (int n = 0; n <= N; n++) {
                if (n < k * A || n > k * B) {
                    f[n][t1] = INF;
                    continue;
                }
                insert(t0, n - A, k);
                f[n][t1] = g[k] * P[n] + get(n - B, opt);
                if (opt == -1) f[n][t1] = INF;
                if (n == N) { 
                    if (f[n][t1] < ans) {
                        ans = f[n][t1];
                        ansk = k;   
                        ansopt = N - opt;                        
                    }
                }
            }
            t0 = t1;
        }
        if (ans == INF) {
            puts("No solution.");
        }
        else {
            printf("%lld %d %d\n", ans, ansk, ansopt);
        }
    }
    return 0;    
}