高效算法设计(二)

在贪心算法的基础上
再加一些辅助的优化和求解策略
比如数据结构优化，扫描线等等

头文件

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <assert.h>


using namespace std;
typedef long long llong;
typedef set<int>::iterator ssii;

const int maxn = 1000 + 10;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)

扫描线行列式优化

POJ2280

const int maxn = 1000 + 10;
int n;

class Point {
public:
    int x, y;
    double deg;

    bool operator< (const Point& rhs) const {
        return deg < rhs.deg;
    }
};

Point mol[maxn], pt[maxn];
int color[maxn];

void init() {
    Set(color, 0);
}

bool det(const Point& A, const Point& B) {
    return A.x * B.y - A.y * B.x >= 0;
}

int solve() {
    if(n <= 2) return 2;

    int ans = 0;

    // update ans
    // i as pivot
    _for(i, 0, n) {
        int k = 0;

        _for(j, 0, n) {
            if(j == i) continue;
            pt[k].x = mol[j].x - mol[i].x;
            pt[k].y = mol[j].y - mol[i].y;
            if(color[j]) {
                pt[k].x = -pt[k].x;
                pt[k].y = -pt[k].y;
            }
            pt[k].deg = atan2(pt[k].y, pt[k].x);

            k++;
        }
        // i as pivot, original point
        // all nodes relative coordinates => pt[0, k)

        sort(pt, pt + k);

        int R = 0, cnt = 2;
        _for(L, 0, k) {
            if(R == L) {
                R = (R + 1) % k;
                cnt++;
            }

            while(R != L && det(pt[L], pt[R])) {
                R = (R + 1) % k;
                cnt++;
            }

            cnt--;
            ans = max(ans, cnt);
        }
    }
    return ans;
}

int main() {
    freopen("input.txt", "r", stdin);
    while(scanf("%d", &n) == 1 && n) {
        init();
        _for(i, 0, n) scanf("%d%d%d", &mol[i].x, &mol[i].y, &color[i]);

        printf("%d\n", solve());
    }
}

贪心模版: 区间扩展

HDU2756

int A[maxn];

void init() {
    Set(A, 0);
}

int main() {
    freopen("input.txt", "r", stdin);
    int kase, n;

    while(scanf("%d", &kase) != EOF) {
        while(kase--) {
            scanf("%d", &n);
            init();
            _for(i, 0, n) scanf("%d", &A[i]);

            set<int> inter;
            int R = 0, ans = 0;
            _for(L, 0, n) {
                while(R < n && !inter.count(A[R])) inter.insert(A[R++]);
                ans = max(ans, R - L);
                inter.erase(A[L]);
            }
            printf("%d\n", ans);
        }
    }
}

单调栈与单调队列

单调栈

POJ2559

const int maxn = 100000 + 10;

class Rec {
public:
    int h, w;
    Rec(int _h = 0, int _w = 0) : h(_h), w(_w) {}

};

int n;
Rec recs[maxn];
llong ans;

stack<Rec> stk;

void init() {
    ans = 0;
    while(!stk.empty()) stk.pop();
}

int main() {
    freopen("input.txt", "r", stdin);
    while (cin >> n && n) {
        init();

        stk.push(Rec(0, 0));
        _rep(i, 1, n + 1) {
            int x;
            if(i == n + 1) x = 0;
            else scanf("%d", &x);

            if(stk.top().h < x) stk.push(Rec(x, 1));
            else {
                int width = 0;
                while (stk.top().h > x) {
                    width += stk.top().w;
                    ans = max(ans, (llong)width * stk.top().h);
                    stk.pop();
                }
                stk.push(Rec(x, width + 1));
            }
        }
        cout << ans << endl;
    }
}

单调队列

最大子序和

const int maxn = 300000 + 10;
int A[maxn];
llong S[maxn];
int n, m;
deque<int> que;

void init() {
    Set(A, 0);
    Set(S, 0);
    while(!que.empty()) que.pop_front();
}

int main() {
    freopen("input.txt", "r", stdin);
    init();

    cin >> n >> m;
    _rep(i, 1, n) {
        scanf("%d", &A[i]);
        S[i] = S[i - 1] + A[i];
    }

    llong ans = 0;
    // use [que.back(), que.front()] to match [i - m, i - 1]
    // ans = max(ans, [que.back(), i])

    que.push_front(0);
    _rep(i, 1, n) {
        while(!que.empty() && que.back() < i - m) que.pop_back();
        ans = max(ans, S[i] - S[que.back()]);
        while(!que.empty() && S[que.front()] >= S[i]) que.pop_front();
        que.push_front(i);
    }
    cout << ans << endl;
}

单调性+区间扩张

涉及单调性优化贪心的问题，往往和一个值的“生存周期”有关
选择生存周期尽量长的
$g[j] \geqslant g[i]$, $i$ 不进入集合，这里要取等
因为 $j$ 位置之前已经出现过了，相当于 $j$ 经历了很多考验
$g[j] = g[i]$ 的时候，更应该保留 $j$

LA4976

const int maxn = 200000 + 10;
int n, a[maxn], f[maxn], g[maxn];

void init() {
    Set(a, 0);
    Set(f, 0);
    Set(g, 0);
}

void initCal() {
    g[0] = 1;
    _for(i, 1, n) {
        if(a[i] > a[i - 1]) g[i] = g[i - 1] + 1;
        else g[i] = 1;
    }

    f[n - 1] = 1;
    _forDown(i, n - 2, 0) {
        if(a[i] < a[i + 1]) f[i] = f[i + 1] + 1;
        else f[i] = 1;
    }
}

class Node {
public:
    int A, g;
    Node(int _A = 0, int _g = 0) : A(_A), g(_g) {}

    bool operator< (const Node& rhs) const {
        return A < rhs.A;
    }
};

typedef set<Node>::iterator sit;

int main() {
    freopen("input.txt", "r", stdin);
    int kase;
    scanf("%d", &kase);

    while(kase--) {
        scanf("%d", &n);
        init();

        _for(i, 0, n) scanf("%d", &a[i]);
        if(n == 1) {
            printf("1\n");
            continue;
        }

        initCal();

        // init calculate f() and g()
        // then solve
        set<Node> tb;
        tb.clear();
        tb.insert(Node(a[0], g[0]));

        int ans = 1;
        _for(i, 1, n) {
            Node cur(a[i], g[i]);
            sit it = tb.lower_bound(cur);

            bool keep = true;
            if(it != tb.begin()) {
                Node last = *(--it);
                int len = last.g + f[i];
                ans = max(ans, len);
                if(cur.g <= last.g) keep = false;
            }

            if(keep) {
                tb.erase(cur);
                tb.insert(cur);

                it = tb.find(cur);
                it++;

                while(it != tb.end() && (it->A > cur.A && it->g <= cur.g)) tb.erase(it++);
            }
        }
        cout << ans << endl;
    }
}

斜率优化

LA4726

const int maxn = 100000 + 10;
int S[maxn], st[maxn];
char str[maxn];

int n, L;

void init() {
    Set(S, 0);
    Set(st, 0);
    Set(str, 0);
}

void initCal() {
    S[0] = 0;
    _rep(i, 1, n) S[i] = S[i - 1] + str[i] - '0';
}

int minusSlope(int x1, int x2, int x3, int x4) {
    return (S[x2] - S[x1 - 1]) * (x4 - x3 + 1) - (S[x4] -S[x3 - 1]) * (x2 - x1 + 1);
}

int main() {
    freopen("input.txt", "r", stdin);
    int kase;
    scanf("%d", &kase);

    while(kase--) {
        init();
        scanf("%d%d%s", &n, &L, str + 1);

        // input finished
        initCal();

        int ansL = 1, ansR = n;
        int l = 0, r = 0;
        _rep(t, L, n) {
            // st[l, r) is candidate start point
            // t - L + 1 represent start point
            // stack st, put value t - L + 1
            while (r - l > 1 && minusSlope(st[r - 2], t - L, st[r - 1], t - L) >= 0) r--;
            st[r++] = t - L + 1;

            // find tangent point st[l]
            // [st[l], t) is the max
            while(r - l > 1 && minusSlope(st[l], t, st[l + 1], t) <= 0) l++;

            int dslp = minusSlope(st[l], t, ansL, ansR);
            if(dslp > 0 || (dslp == 0 && t - st[l] < ansR - ansL)) {
                ansL = st[l];
                ansR = t;
            }
        }
        printf("%d %d\n", ansL, ansR);
    }
}