初级动态规划: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$ 要从后向前枚举,因为每次的新结果都是根据上一个结果来求得的,从后向前可避免重复取同一物品。

阅读更多

搜索与状压 DP

DFS

搜索和DP不分家,几乎所有的DP都能用搜索解决(虽然复杂度可能较劣)。不过,如果实在想不出正解,DFS不失为骗分的好手段。

主要的搜索算法有:

  1. DFS/BFS爆搜
  2. 双向BFS
  3. 启发式搜索(又称A*)
  4. 迭代加深搜索
  5. IDA*(迭代加深+启发式)
  6. 记忆化搜索
  7. 剪枝

重要程度:1,7,6 > 4,3 > 5,2。

阅读更多

高级动态规划:区间、树形

区间 DP

P1880 [NOI1995]石子合并

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 <iostream>
using namespace std;

const int N = 220;

int ans, dp[N][N], n, a[N], s[N];

int main() {

scanf("%d", &n);
for(int i=1; i<=n; ++i) {
scanf("%d", a+i);
s[i] = s[i-1] + a[i];
}
for(int i=1; i<=n; ++i) {
s[i+n] = s[i+n-1] + a[i];
}
memset(dp, 0x3f, sizeof dp);
for(int i=1; i<=2*n; ++i) dp[i][i] = 0;
for(int l=2; l<=n; ++l) {
for(int i=1, j=l; j<=2*n; ++i, ++j) {
for(int k=i; k<j; ++k) {
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + s[j] - s[i-1]);
}
}
}
ans = 0x3f3f3f3f;
for(int i=1; i<=n; ++i) {
//printf("%d ", dp[i][i+n-1]);
ans = min(ans, dp[i][i+n-1]);
}
printf("%d\n", ans);

memset(dp, 0, sizeof dp);
for(int i=1; i<=2*n; ++i) dp[i][i] = 0;
for(int l=2; l<=n; ++l) {
for(int i=1, j=l; j<=2*n; ++i, ++j) {
for(int k=i; k<j; ++k) {
dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j] + s[j] - s[i-1]);
}
}
}
ans = 0;
for(int i=1; i<=n; ++i) {
ans = max(ans, dp[i][i+n-1]);
}
printf("%d\n", ans);
return 0;
}

P1063 能量项链

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

int n, h[N], t[N], dp[N][N];
int main() {

scanf("%d", &n);
for(int i=1; i<=n; ++i) {
scanf("%d", &h[i]);
h[i+n] = h[i];
}
for(int i=1; i<2*n; ++i) t[i] = h[i+1];

for(int l=2; l<=n; ++l) {
for(int i=1, j=l; j<=2*n; ++i, ++j) {
for(int k=i; k<j; ++k) {
dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j] + h[i] * t[k] * t[j]);
}
}
}
int ans = 0;
for(int i=1; i<=n; ++i) {
ans = max(ans, dp[i][i+n-1]);
}
printf("%d\n", ans);
return 0;
}


P3146 [USACO16OPEN]248 G

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

int n, dp[300][300], ans = 0;
int main() {

scanf("%d", &n);
for(int i=1; i<=n; ++i) {
scanf("%d", &dp[i][i]);
}

for(int l=2; l<=n; ++l) {
for(int i=1, j=l; j<=n; ++i, ++j){
for(int k=i; k<j; ++k) {
if(dp[i][k] == dp[k+1][j])
dp[i][j] = max(dp[i][j], dp[i][k]+1);
}
ans = max(ans, dp[i][j]);
}
} printf("%d\n", ans);
return 0;
}

树形 DP

树形DP三大问题:树的最大独立集 树的重心 树的最长路径

阅读更多