初级动态规划:LIS、LCS、背包

LIS & LCS

P1020 导弹拦截

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
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n = 0;

int a[N], b[N], s[N], ls[N];
void add(int x, int v) {
for(; x<=n; x+=x&(-x)) s[x] = max(s[x], v);
}

int query(int x) {
int ans = 0;
for(; x>0; x-=x&(-x)) ans = max(ans, s[x]);
return ans;
}
int main() {
//freopen("p1020_1.in", "r", stdin);
for(; scanf("%d", a+n+1) != EOF; ++n, b[n] = a[n]);

sort(b+1, b+n+1);
int t = unique(b+1, b+n+1) - (b+1);

for(int i=1; i<=n; ++i)
a[i] = lower_bound(b+1, b+t+1, a[i]) - b;

int ans = 0;
for(int i=n; i>0; --i) {
int q = query(a[i]) + 1;
add(a[i], q);
ans = max(ans, q);
}
printf("%d\n", ans);

ans = 0;
memset(s, 0, sizeof s);
for(int i=1; i<=n; ++i) {
int q = query(a[i]-1) + 1;
add(a[i], q);
ans = max(ans, q);
}
printf("%d\n", ans);
return 0;
}

P1439 【模板】最长公共子序列

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
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;

const int N = 100010;

int n, b[N], p1[N], p2[N], s[N];

int lowbit(int x) {
return x&(-x);
}
void add(int x, int v) {
for(; x <= n; x += lowbit(x)) s[x] = max(s[x], v);
}
int query(int x) {
int ans = 0;
for(; x > 0; x -= lowbit(x)) ans = max(ans, s[x]);
return ans;
}
int main() {

scanf("%d", &n);
for(int i=1; i<=n; ++i) scanf("%d", p1+i);
for(int i=1; i<=n; ++i) scanf("%d", p2+i);

for(int i=1; i<=n; ++i) b[p1[i]] = i;
for(int i=1; i<=n; ++i) p2[i] = b[p2[i]];

int ans = 0;
for(int i=1; i<=n; ++i) {
int q = query(p2[i]-1) + 1;
add(p2[i], q);
ans = max(ans, q);
}

printf("%d", ans);
return 0;
}

0-1 背包

$$
F(i,j)=
\begin{cases}
F(i-1,j)& j \leq w_i\\
\max{F(i-1,j),F(i-1,j-w_i)+v_i}& j > w_i
\end{cases}
$$

注意二维转换成一维的时候,$j$ 要从后向前枚举,因为每次的新结果都是根据上一个结果来求得的,从后向前可避免重复取同一物品。

P2196 挖地雷

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
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <vector>
using namespace std;
const int N = 30;

typedef pair <int, vector<int> > piv;
vector<int> g[N];

int s1[N], n, w[N], in[N];
vector<int> ss[N];

piv ans;

void outp(vector<int> &ans) {
for(vector<int>::iterator it = ans.begin(); it != ans.end(); ++it)
printf("%d ", *it);
printf("\n");
}

piv dfs(int x, vector<int> s) {
if(s1[x]) {
return (piv){s1[x], ss[x]};
}
if(g[x].size() == 0) {
s1[x] = w[x]; ss[x].clear(); ss[x].push_back(x);
return (piv){s1[x], ss[x]};
}
s1[x] = w[x];
ss[x].push_back(x);
vector<int> st = ss[x];

for(vector<int>::iterator it = g[x].begin(); it != g[x].end(); ++it) {
piv p = dfs(*it, s);
if(p.first + w[x] > s1[x]) {
s1[x] = p.first + w[x];
ss[x] = st;
ss[x].insert(ss[x].end(), p.second.begin(), p.second.end());
}
}
return (piv){s1[x], ss[x]};
}

int main() {

scanf("%d", &n);
for(int i=1; i<=n; ++i) scanf("%d", w+i);
for(int i=1, a; i<=n; ++i) {
for(int j=i+1; j<=n; ++j) {
scanf("%d", &a);
if(a) g[i].push_back(j), ++in[j];
}
}

for(int i=1; i<=n; ++i) {
if(!in[i]) {
piv p = dfs(i, ss[i]);
if(p.first > ans.first) {
ans.first = p.first;
ans.second.clear();
ans.second.insert(ans.second.end(), p.second.begin(), p.second.end());
}
}
}

outp(ans.second);
printf("%d", ans.first);

return 0;
}

P1455 搭配购买

套一个并查集。

Code:(2019.12.01)

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
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>

const int N = 11000;

struct node {
int c, d;
} val[N], tmp[N];

int n, m, w, fa[N], list[N], dp[N], t, ans = 0;
bool flag[N];

int root(int x) {
return fa[x] == x ? x : fa[x] = root(fa[x]);
}

void operator +=(node &A, node B) {
A.c += B.c, A.d += B.d;
}

int main() {

scanf("%d%d%d", &n, &m, &w);

for(int i=1; i<=n; ++i) fa[i] = i;
for(int i=1; i<=n; ++i) scanf("%d%d", &val[i].c, &val[i].d);

for(int i=1; i<=m; ++i) {
int u, v;
scanf("%d%d", &u, &v);
int u1 = root(u), v1 = root(v);
fa[u1] = v1;
}
for(int i=1; i<=n; ++i) root(i);

for(int i=1; i<=n; ++i) tmp[fa[i]] += val[i];

memcpy(list+1, fa+1, n*4);
std::sort(list+1, list+n+1);
t = std::unique(list+1, list+n+1) - (list+1);

for(int i=1; i<=t; ++i)
for(int j=w; j>=tmp[list[i]].c; --j)
dp[j] = std::max(dp[j], dp[j - tmp[list[i]].c] + tmp[list[i]].d);

printf("%d\n", dp[w]);

return 0;
}

P1164 小A点菜

这怎么会是橙题啊

注意DP的初值 dp[0] = 1,因为需特别考虑过程中「从0开始买菜」的情况。

循环中的i 表示已经考虑到了前i道菜。如果能买的起,就直接把 dp[j-a[i]] 转移过来,否则不变。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;

int dp[11000], n, m, a[110];

int main() {

scanf("%d%d", &n, &m);
for(int i=1; i<=n; ++i) scanf("%d", &a[i]);

dp[0] = 1;
for(int i=1; i<=n; ++i) {
for(int j=m; j>=a[i]; --j) {
dp[j] += dp[j-a[i]];
}
}

printf("%d\n", dp[m]);
return 0;
}

完全背包

与上面的01背包问题差别不大,只是多了一个条件:每个物品可以取无数次。

方法很简单,只要 $j$ 从前向后枚举即可。这样做其实是变相利用了它的后效性,使同一个物品可以被多次取到。

P1616 疯狂的采药

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;

int t1, m, dp[int(1e7+10)], t[int(1e4+10)], v[int(1e4+10)];
int main() {

scanf("%d%d", &t1, &m);
for(int i=1; i<=m; ++i) scanf("%d%d", t+i, v+i);
for(int i=1; i<=t1; ++i) {
dp[i] = dp[i-1];
for(int j=1; j<=m; ++j)
if(i-t[j]>=0) dp[i] = max(dp[i], dp[i-t[j]] + v[j]);
}

printf("%d\n", dp[t1]);
return 0;
}

多重背包

一种方法是转化成 01 背包处理。

首先找到最大的 $k$ 使得 $t=\sum_{i=0}^{k}2^i(t < c_i)$,也就是找到最大的小于 $c_i$ 的二的各个次幂和。这样之后,我们就可以通过不重复且有选择地使用 $2^0$到 $2^k$ 来表示出 1到 t所有的数。但是剩下的呢?我们将剩下的 $c_i-t$ 单独分成一个物品,因为 1到 t都可以表示,那么有了这个 $c_i-t$ 物品,就可以表示出所有数了。

例如,把 $21$ 分为 $[1,2,4,8,6]$,这样就可以从中不重复地选择来表示出 1到 $c_i$ 的所有数了。

P1776 宝物筛选

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;

const int N = 110, M = 44000;

int n, W, v[N], w[N], m[N], dp[M];
int main() {
scanf("%d%d", &n, &W);
for(int i=1; i<=n; ++i) scanf("%d%d%d", v+i, w+i, m+i);

for(int i=1; i<=n; ++i) {
//1, 2, 4, 8, ... 2^k, m_i-2^(k+1)+1
int sum = 0;
for(int j=0; sum + (1<<j) <= m[i]; ++j) {
sum += (1<<j);
for(int l=W; l>=w[i]*(1<<j); --l)
dp[l] = max(dp[l], dp[l-w[i]*(1<<j)] + v[i]*(1<<j));
}
for(int l=W; l>=w[i]*(m[i] - sum); --l)
dp[l] = max(dp[l], dp[l-w[i]*(m[i] - sum)] + v[i]*(m[i] - sum));
}
printf("%d\n", dp[W]);
return 0;
}

P5020 [NOIP2018提高组]货币系统

首先要想到这题可能并不是数论。

80分做法:

考虑爆搜,枚举现有系统中的每个数能否被其他已选择的数表示出来。这里可以贪心的想,如果一个数能被另外几个数表示,那么删除它一定是更优解。

dfs() 部分可以换成背包,不过复杂度级别是差不多的。

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
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 110;

bool us[N];
int T, n, maxv, t, a[N];
bool dfs(int s, int x, int p) {
if(x > n or s > a[p]) return false;
if(x == p or us[x]) return dfs(s, x+1, p);
for(int i=0; i<=maxv/a[x]; ++i) {
if(s+a[x]*i == a[p]) return true;
bool f = dfs(s+a[x]*i, x+1, p);
if(f) return true;
}
return false;
}
int main() {

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

maxv = 0;
for(int i=1; i<=n; ++i) {
scanf("%d", a+i);
maxv = max(maxv, a[i]);
}

sort(a+1, a+n+1);
t = unique(a+1, a+n+1) - (a+1); int ans = t;

memset(us, false, sizeof us);
for(int i=1; i<=t; ++i) {
if(dfs(0,1,i)) {
us[i] = true;
--ans;
}
}

printf("%d\n", ans);
}
return 0;
}

满分做法:

其实在80分基础上再多想一步就够了:我们不用枚举每个数的表示法来判断可不可以删。直接对所有数dp,如果一个数能用一种以上的方式表示出来,那么就删掉它。显然删掉这个数是无后效的。

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
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 110;

bool us[N]; int dp[26000];
int T, n, maxv, t, a[N];

int main() {

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

maxv = 0;
for(int i=1; i<=n; ++i) {
scanf("%d", a+i);
maxv = max(maxv, a[i]);
}

sort(a+1, a+n+1);
t = unique(a+1, a+n+1) - (a+1); int ans = t;

memset(dp, 0, sizeof dp);
dp[0] = 1;
for(int i=1; i<=t; ++i) {
for(int j=a[i]; j<=maxv; ++j) {
dp[j] += dp[j-a[i]];
}
}
for(int i=1; i<=t; ++i) {
if(dp[a[i]] > 1) --ans;
}

printf("%d\n", ans);
}
return 0;
}

分组背包

在枚举主件的前提下枚举附件。

P1064 金明的预算方案

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
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <vector>
using namespace std;

const int N = 33000, M = 65;

typedef vector<int>::iterator IT;
int n, m, p[M], v[M], dp[N];
int g[M][2];
vector<int> s;
int main() {

//freopen("P1064_5.in","r",stdin);

scanf("%d%d", &n, &m);
for(int i=1; i<=m; ++i) { int q;
scanf("%d%d%d", &v[i], &p[i], &q);
if(q == 0) s.push_back(i);
else if(g[q][0]) g[q][1] = i; else g[q][0] = i;
}

for(IT it = s.begin(); it != s.end(); it++) {
int i = *it;
int a = g[i][0], b = g[i][1];
for(int j=n; j>=v[i]; --j) {
dp[j] = max(dp[j], dp[j-v[i]] + v[i]*p[i]);
if(j-v[i]-v[a] >= 0) dp[j] = max(dp[j], dp[j-v[i]-v[a]] + v[i]*p[i] + v[a]*p[a]);
if(j-v[i]-v[b] >= 0) dp[j] = max(dp[j], dp[j-v[i]-v[b]] + v[i]*p[i] + v[b]*p[b]);
if(j-v[i]-v[a]-v[b] >= 0)
dp[j] = max(dp[j], dp[j-v[i]-v[a]-v[b]]
+ v[i]*p[i] + v[a]*p[a] + v[b]*p[b]);
}
}
printf("%d\n", dp[n]);
return 0;
}

装满背包

一种特殊情况。

背包不一定装满时,$dp[j]$ 记录的是前i件物品放入空间为j的背包中的最大价值,要在一开始,让 $dp[]$ 中的每个值为 0。

背包装满时,注意要把 f[j](表示刚好装满的最大价值)初始化为 f[0] = 0; f[1..n] = -INF;,这样就能使那些能够恰好装满背包的物品的值为正数,而那些不能恰好装满背包的物品的值就为负数,就容易区分了。

dp[n(背包最多承重)] == inf 的话,说明装不满;如果装满的话,dp[n] 即为最高价值。

初级动态规划:LIS、LCS、背包

https://snow.js.org/dp-linear/

发布于

2020-11-01

更新于

2022-08-02

许可协议

评论