水题笔记_ codevs 线段覆盖 1 ~ 5 [贪心, DP]

看上去相似的题目解法却千差万别

懵逼的 题目

传送至 Codevs

扯淡的 题解

第一题贪心, 和第三题一样 只不过数据范围不同…
第二题序列DP 我沙茶的写成了离散化 × 背包
第四题和第二题一样 序列DP 只不过数据范围不一样
第五题离散化 × 序列DP

  • 贪心就是给右端点排序, 然后枚举线段, 能放就放
  • DP 就是, f[i] 代表坐标为 0 ~ i 能取到的最大的价值, f[i] = f[i - 1]; f[i] = max(f[i], f[当前线段的右端点] + 当前线段的价值);

没了…是不是很水?

沙茶的 代码

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
//线段覆盖 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define INF (999)
#define MAXN (100 + 5)
using namespace std;
struct xd
{
int lx;
int rx;
}a[MAXN];
int n;
int ans;
bool cmp(xd, xd);
void tx();
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d%d", &a[i].lx, &a[i].rx);
if (a[i].lx > a[i].rx)
swap(a[i].lx, a[i].rx);
}
tx();
printf("%d", ans);
}
void tx()
{
sort(a + 1, a + n + 1, cmp);
int dqr = -INF + 1;
for (int i = 1; i <= n; i++)
{
if (a[i].lx >= dqr && a[i].rx < INF)
{
dqr = a[i].rx;
ans++;
}
}
}
bool cmp(xd x, xd y)
{
return x.rx < y.rx;
}
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
//线段覆盖2 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define INF (1000000)
#define MAXN (2000 + 5)
using namespace std;
struct lsh
{
int zhi;
int belong;
bool lorr;
}b[MAXN * 2];
struct xd
{
int l;
int r;
int c;
}a[MAXN];
int n;
int g[MAXN][MAXN];
int f[MAXN * 2];// f[i] 代表以i为结尾的序列的最大价值
void init();
bool cmp(lsh, lsh);
void dp();
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d%d%d", &a[i].l, &a[i].r, &a[i].c);
b[i].zhi = a[i].l; b[i + n].zhi = a[i].r;
b[i + n].belong = b[i].belong = i;
b[i].lorr = false; b[i + n].lorr = true;
}
init();
/*for (int i = 1; i <= n; i++)
{
printf("%d %d %d\n", a[i].l, a[i].r, a[i].c);
}*/
dp();
printf("%d", f[2 * n]);
return 0;
}
bool cmp(lsh x, lsh y)
{
return x.zhi < y.zhi;
}
void init()
{
sort(b + 1, b + n + n + 1, cmp);
int zb = 0;
for (int i = 1; i <= n + n; i++)
{
if (b[i].lorr)
{
a[b[i].belong].r = zb;
}
else
{
a[b[i].belong].l = zb;
}
if (b[i].zhi != b[i + 1].zhi)
zb++;
}
memset(g, 0, sizeof(g));
for (int i = 1; i <= n; i++)
{
if (!g[a[i].l][a[i].r])
{
g[a[i].l][a[i].r] = i;
}
else
{
if (a[i].c > a[g[a[i].l][a[i].r]].c)
{
g[a[i].l][a[i].r] = i;
}
}
}
}
void dp()
{
memset(f, 0, sizeof(f));
for (int i = 0; i <= n + n; i++)
{
if (i - 1 >= 0)
f[i] = f[i - 1];
for (int j = 0; j <= i; j++)
{
if (g[j][i])
{
f[i] = max(f[i], f[j] + a[g[j][i]].c);
}
}
}
}
/*
10
0 3 4
1 4 7
15 19 8
1 2 6
1 3 4
2 5 6
4 7 7
2 4 3
3 8 10
7 12 2
*/
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
//线段覆盖3 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define INF (1000000 + 5)
#define MAXN (1000000 + 5)
using namespace std;
struct xd
{
int lx;
int rx;
}a[MAXN];
int n;
int ans;
bool cmp(xd, xd);
void tx();
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d%d", &a[i].lx, &a[i].rx);
if (a[i].lx > a[i].rx)
swap(a[i].lx, a[i].rx);
}
tx();
printf("%d", ans);
}
void tx()
{
sort(a + 1, a + n + 1, cmp);
int dqr = -INF + 1;
for (int i = 1; i <= n; i++)
{
if (a[i].lx >= dqr && a[i].rx < INF)
{
dqr = a[i].rx;
ans++;
}
}
}
bool cmp(xd x, xd y)
{
return x.rx < y.rx;
}
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
//线段覆盖4 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#define MAXN (1000000 + 5)
#define INF (1000000)
#define LL long long
using namespace std;
struct xd
{
int lside;
int weight;
xd(int l, int w): lside(l), weight(w) {}
};
vector <xd> lx[INF + 5];
int n;
LL f[MAXN];
void dp();
int main()
{
scanf("%d", &n);
int srx, sry, src;
for (int i = 1; i <= n; i++)
{
scanf("%d%d%d", &srx, &sry, &src);
lx[sry].push_back(xd(srx, src));
}
dp();
printf("%lld", f[INF]);
return 0;
}
void dp()
{
f[0] = 0;
for (int i = 0; i <= INF; i++)
{
if (i - 1 >= 0)
f[i] = f[i - 1];
for (int j = 0; j < lx[i].size(); j++)
{
f[i] = max(f[i], (LL)f[lx[i][j].lside] + lx[i][j].weight);
}
}
}
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
85
86
//线段覆盖5 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#define LL long long
#define INF (2000000)
#define MAXN (1000000 + 5)
#define max(a, b) ((a) > (b) ? (a) : (b))
using namespace std;
struct cxd
{
LL lside;
LL rside;
int weight;
}a[MAXN];
struct xd
{
int lside;
int weight;
xd(int l, int w): lside(l), weight(w) {}
};
struct node
{
LL zb;
int belong;
bool is_left;
}c[MAXN * 2];
int n;
LL f[INF + 5];
vector <xd> lx[INF];
void dp();
void init();
bool cmp(node, node);
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%lld%lld%d", &a[i].lside, &a[i].rside, &a[i].weight);
c[i].belong = c[i + n].belong = i;
c[i].zb = a[i].lside; c[i + n].zb = a[i].rside;
c[i].is_left = true; c[i + n].is_left = false;
}
init();
dp();
printf("%lld", f[INF]);
return 0;
}
bool cmp(node x, node y)
{
return x.zb < y.zb;
}
void init()
{
sort(c + 1, c + n + n + 1, cmp);
int cnt = 1;
for (int i = 1; i <= n + n; i++)
{
if (c[i].is_left)
a[c[i].belong].lside = cnt;
else
a[c[i].belong].rside = cnt;
if (c[i].zb != c[i + 1].zb)
++cnt;
}
for (int i = 1; i <= n; i++)
{
lx[a[i].rside].push_back(xd(a[i].lside, a[i].weight));
}
}
void dp()
{
f[0] = 0;
for (int i = 1; i <= INF; i++)
{
f[i] = f[i - 1];
for (int j = 0; j < lx[i].size(); j++)
{
f[i] = max(f[i], (LL)f[lx[i][j].lside] + lx[i][j].weight);
}
}
}

By 文化课爆炸的 Cansult