CodeForces - 714E + POJ - 3666 （dp严格单调递增与非严格单调递增） - JavaScript

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

左偏树

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

虽然题目要求比论文多了一个条件，但是……只需要求非递减就可以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 = ;

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 = ;

    tr[cnt_tr].sz = ;

    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 + ;

    tr[x].sz = tr[tr[x].l].sz + tr[tr[x].r].sz + ;

    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 = ;

        for (int i = ; i < n; ++i) {

            scanf("%d", a+i);

            sum += a[i];

        }

        int cnt = ;

        for (int i = ; i < n; ++i) {

            root[++cnt] = NewTree(a[i]);

            num[cnt] = ;

            while (cnt >  && Top(root[cnt]) < Top(root[cnt-])) {

                cnt--;

                root[cnt] = Merge(root[cnt], root[cnt+]);

                num[cnt] += num[cnt+];

                while (tr[root[cnt]].sz* > num[cnt]+) Pop(root[cnt]);

            }

        }

        int px = ;

        for (int i = ; i <= cnt; ++i)

            for (int j = , x = Top(root[i]); j < num[i]; ++j)

                tmp += abs(a[px++]-x);

        ans = tmp;

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

    }

    return ;

}

－－－－

考虑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 = ;

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 = ; i <= n; ++i) {

        scanf("%d", a+i);

        b[i] = a[i];

    }

    sort(b+, b++n);

    int last;

    for (int i = ; i <= n; ++i) {

        last = INF;

        for (int j = ; j <= n; ++j) {

            last = min(last, dp[i-][j]);

            dp[i][j] = fabs(b[j]-a[i]) + last;

        }

    }

    int ans = INF;

    for (int i = ; i <= n; ++i) {

        ans = min(ans, dp[n][i]);

    }

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

    return ;

}

贪心

https://blog.csdn.net/lycheng1215/article/details/80089004

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <queue>

using namespace std;

const int maxn = 2e5 + ;

int a[maxn];

priority_queue<int>s;

int main(int argc, char const *argv[])

{

    int n;

   scanf("%d", &n);

    long long ans = ;

    for(int i = ;i <= n ; i ++) {

         scanf("%d", &a[i]);

        //a[i] -= i;

        s.push(a[i]);

        if(s.top() > a[i]){

            ans += s.top() - a[i];

            s.pop();

            s.push(a[i]);

        }

    }

    printf("%d",ans);

    return ;

}