POJ3666-Making the Grade（左偏树 or DP）

左偏树

炒鸡棒的论文《左偏树的特点及其应用》

虽然题目要求比论文多了一个条件，但是……只需要求非递减就可以AC……数据好弱……

虽然还没想明白为什么，但是应该觉得应该是这样——求非递减用大顶堆，非递增小顶堆……

这题和bzoj1367题意差不多，但是那题求的是严格递增。（bzoj找不到那道题，可能是VIP或什么原因？

严格递增的方法就是每一个数字a[i]都要减去i，这样求得的b[i]也要再加i，保证了严格递增（为什么对我就不知道了

代码比较水，因为题目数据的问题，我的代码也就钻了空子，反正ac就好了。。。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 2005;
typedef long long ll;

struct LTree {
    int l, r, sz;
    int key, dis;
    bool operator<(const LTree lt) const {
        return key < lt.key;
    }
} tr[N];
int cnt_tr;

int NewTree(int k) {
    tr[++cnt_tr].key = k;
    tr[cnt_tr].l = tr[cnt_tr].r = tr[cnt_tr].dis = 0;
    tr[cnt_tr].sz = 1;
    return cnt_tr;
}

int Merge(int x, int y) {
    if (!x || !y) return x + y;
    if (tr[x] < tr[y]) swap(x, y);
    tr[x].r = Merge(tr[x].r, y);
    if (tr[tr[x].l].dis < tr[tr[x].r].dis) swap(tr[x].l, tr[x].r);
    tr[x].dis = tr[tr[x].r].dis + 1;
    tr[x].sz = tr[tr[x].l].sz + tr[tr[x].r].sz + 1;
    return x;
}

int Top(int x) {
    return tr[x].key;
}

void Pop(int &x) {
    x = Merge(tr[x].l, tr[x].r);
}

int a[N], root[N], num[N];

int main() {
    int n;
    while (~scanf("%d",&n)) {
        ll sum, tmp, ans;
        cnt_tr = sum = tmp = 0;
        for (int i = 0; i < n; ++i) {
            scanf("%d", a+i);
            sum += a[i];
        }
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            root[++cnt] = NewTree(a[i]);
            num[cnt] = 1;
            while (cnt > 1 && Top(root[cnt]) < Top(root[cnt-1])) {
                cnt--;
                root[cnt] = Merge(root[cnt], root[cnt+1]);
                num[cnt] += num[cnt+1];
                while (tr[root[cnt]].sz*2 > num[cnt]+1) Pop(root[cnt]);
            }
        }
        int px = 0;
        for (int i = 1; i <= cnt; ++i)
            for (int j = 0, x = Top(root[i]); j < num[i]; ++j)
                tmp += abs(a[px++]-x);
        ans = tmp;

        printf("%lld\n", ans);
    }
    return 0;
}

这题DP也很神奇，挖坑，明天学……

－－－－

考虑dp，dp[i][j]表示前i个数，最后一个数是j的最小花费

dp方程：dp[i][j]=min(dp[i-1][k], k≤j) ＋ abs(a[i]-j)

j的范围1e9，是因为对于每一个i来说，当最优解的时候j一定是a数列中的数，所以只需枚举a数列中的值就可以了。

容易想到dp[i-1][k]就不需要另外一层循环就了，同时可以使用滚动数组（不使用明显也够

上面求的是不减，求不增把数组到倒过来就可以了。（懒，没写。。

时间复杂度O(n^2)，比上面左偏树明显慢了不少。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 2005;
const int INF = 0x5f5f5f5f;

int dp[N][N];
int a[N], b[N];
int main() {
    //freopen("in", "r", stdin);
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a+i);
        b[i] = a[i];
    }
    sort(b+1, b+1+n);
    int last;
    for (int i = 1; i <= n; ++i) {
        last = INF;
        for (int j = 1; j <= n; ++j) {
            last = min(last, dp[i-1][j]);
            dp[i][j] = fabs(b[j]-a[i]) + last;
        }
    }
    int ans = INF;
    for (int i = 1; i <= n; ++i) {
        ans = min(ans, dp[n][i]);
    }

    printf("%d\n", ans);

    return 0;
}