HDU4261 WA 求调

rt /kel

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h> 

using namespace std;

typedef long long ll;
typedef double db;

const int MAXN = 2e3 + 10;

priority_queue<int> q1;
priority_queue<int, vector<int>, greater<int>> q2;

ll s1, s2;

inline 
void clear() {
    for (s1 = 0; !q1.empty(); q1.pop());
    for (s2 = 0; !q2.empty(); q2.pop());
}

inline 
void insert(int x) {
    q2.empty() || x > q2.top() ? q2.push(x), s2 += x : (q1.push(x), s1 += x);
    if (q1.size() > q2.size() + 1) { s2 += q1.top(), s1 -= q1.top(), q2.push(q1.top()), q1.pop(); }
    if (q2.size() > q1.size() + 1) { s1 += q2.top(), s2 -= q2.top(), q1.push(q2.top()), q2.pop(); }
}

inline 
ll query() {
    ll x = q1.size() > q2.size() ? q1.top() : q2.top();
    return (q1.size() - q2.size()) * x - s1 + s2;
}

int n, m, a[MAXN];

ll f[MAXN][MAXN], dp[MAXN][30];

int main() {
    for (; scanf("%d%d", &n, &m), n | m;) {
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        for (int i = 1; i <= n; i++) {
            clear();
            for (int j = i; j; j--) insert(a[j]);
        }
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) dp[i][j] = 0x3f3f3f3f3f3f3f3fll;
        }
        **dp = 0;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i && j <= m; j++) {
                for (int k = 1; k <= i; k++) {
                    dp[i][j] = min(dp[i][j], dp[k - 1][j - 1] + f[k][i]);
                }
            }
        }
        printf("%lld\n", dp[n][m]);
    }
}