高效算法设计(二)

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

头文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#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
POJ2280
POJ2280-02

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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
POJ2559

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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;
}
}

单调队列

最大子序和
MaxSubseq

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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] >= g[i], i不进入集合,这里要取等
因为j位置之前已经出现过了,相当于j经历了很多考验
g[j] == g[i]的时候,更应该保留j

LA4976
LA4976

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
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

LA4726-01
LA4726-02

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
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);
}
}