hdu1024 Max Sum Plus Plus的另一种解法

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=1024

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1053

【题解】

原来的解法：http://www.cnblogs.com/galaxies/p/hdu1024.html

原来的解法思路是正着，我们加数，现在考虑删数

我们先特判几种情况（可以全选正，全选正还不够）

现在只剩下一种情况，段数<正数段数

我们可以把数字合并变成+/-/+/-...这个情况

那我们考虑的是合并。

每次我们选出+的段，意为舍弃这一段

选出-的段，意为把这一段和旁边两个正段合并

所以选出代表要把这段绝对值从答案里减去，我们希望越小越好，所以维护一个小根堆（或set）

那么合并的时候把选出的段和旁边两段直接相加即可，由于这个绝对值是最小的，所以加起来还是旁边两段的符号。

特别注意如果在边界上出现了负数那么这个负数是没有任何用的，因为我们选他不能合并来使段数减小，所以直接删掉即可。

在进队列的时候如果边界上出现了0，那么一样把它删掉，因为选0一定是出现这种情况

10000 -10000 -10000 ....

然后你选了第一个，变成了0 -10000 ...

很明显我们第一次选了10000，意为舍弃它，并合并，所以和周围合并变成了0，再选0，没有任何意义，不能使段数减小，反而增加。

至于为什么不能在取top的时候判，因为会有这种情况

m=1,n=4,a[]={0,-1,-1,0}

原本是0，就已经合法，是有实际意义的，所以不能判掉。

然后就过了

# include <set>

# include <stdio.h>

# include <string.h>

# include <iostream>

# include <algorithm>

// # include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

const int M = 1e6 + ;

const int mod = 1e9+;

# define RG register

# define ST static

ll a[M], ans = ;

int m, n;

int p[M], pn;

int tot1, tot2;

set< pair<ll, int> > s;

inline int sgn(int x) {return x<?:;}

inline ll myabs(ll x) {return x>?x:-x;}

inline void transform() {

    n = ;

    ll t = p[]; int s = sgn(t);

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

        if(sgn(p[i]) == s)

            t += p[i];

        else {

            a[++n] = t;

            t = p[i];

            s = sgn(t);

        }

    }

    a[++n] = t;

//    for (int i=1; i<=n; ++i) printf("%d ", a[i]);

}

int Minus[M];

inline void solve_minus() {

    int tn = , tem = m-tot1;

    for (int i=; i<=pn; ++i) if(p[i] < ) Minus[++tn] = p[i];

    sort(Minus+, Minus+tn+);

    while(tem--) ans += Minus[tn--];

}

int L[M], R[M];

inline void del(int x) {

    L[R[x]] = L[x];

    R[L[x]] = R[x];

}

inline void solve() {

    s.clear();

    int T = tot2 - m;

    for (int i=; i<=n+; ++i) L[i] = R[i] = ;

    for (int i=; i<n; ++i) L[i] = i-, R[i] = i+;

    L[n] = n-;

    for (int i=; i<=n; ++i) s.insert(make_pair(myabs(a[i]), i));

//    cout << T << endl;

    while(T--) {

        pair<ll, int> top = *s.begin();

        s.erase(top);

        int x = top.second, y;

        if(a[x] <  && (!L[x] || !R[x])) {

            del(x);

            ++T;

            continue;

        }

        ll sum = a[x];

        ans -= myabs(sum);

        if(L[x]) {

            y = L[x];

            sum += a[y];

            s.erase(make_pair(myabs(a[y]), y));

            del(L[x]);

        }

        if(R[x]) {

            y = R[x];

            sum += a[y];

            s.erase(make_pair(myabs(a[y]), y));

            del(R[x]);

        }

        a[x] = sum;

        if(sum == ) del(x);

        else s.insert(make_pair(myabs(a[x]), x));

    }

}

int main() {

    while(cin >> m >> pn) {

        tot1 = tot2 = ;

        for (int i=; i<=pn; ++i) scanf("%d", p+i);

        transform();

        for (int i=; i<=pn; ++i) tot1 += (p[i] >= );

        for (int i=; i<=n; ++i) tot2 += (a[i] >= );

        ans = ;

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

            if(a[i] >= ) ans += a[i];

//        for (int i=1; i<=n; ++i) cout << a[i] << ' ';

//        cout << endl;

//        cout << "ans = " << ans << endl;

        if(tot2 <= m && m <= tot1) cout << ans << endl;

        else if(m > tot1) {

            solve_minus();

            cout << ans << endl;

        } else {

            solve();

            cout << ans << endl;

        }

    }

    return ;

}