区间DP && 树形DP
Eva.Q Lv9
2022-01-26 10:19:07

But the well is not easy to find.

区间DP

  1. 枚举区间长度
  2. 枚举区间起点
  3. 枚举分割点
石子合并
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<bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
  int x = 0;
  bool f = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f |= (c == '-');
  for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return f ? -x : x;
}

int f[507][507], a[507], s[507];

int main() {
    int n = rd();
    for (int i = 1; i <= n; ++i) {
        a[i] = rd(); s[i] = s[i - 1] + a[i];
    }
    memset(f, 127, sizeof(f));
    for (int i = 1; i <= n; ++i) f[i][i] = 0;
    for (int i = 1; i < n; ++i) {
        for (int j = 1; j <= n - i; ++j) {
            for (int k = j; k < j + i; ++k) {
                f[j][j + i] = min(f[j][j + i], f[j][k] + f[k + 1][j + i] + s[j + i] - s[j - 1]);
            }
        }
    }
    printf("%d\n", f[1][n]);
    return 0;
}
石子合并2

思路1：把环拆成线，枚举拆哪条边

思路2：把环拆成线，再倍长这个线，用“石子合并”的思路就可以做

这里采用思路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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
  int x = 0;
  bool f = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f |= (c == '-');
  for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return f ? -x : x;
}

int f[507][507], a[507], s[507];

int main() {
    int n = rd();
    for (int i = 1; i <= n; ++i) {
        a[i] = a[i + n] = rd();
    }
    n *= 2;
    for (int i = 1; i <= n; ++i) {
        s[i] = s[i - 1] + a[i];
    }
    memset(f, 127, sizeof(f));
    for (int i = 1; i <= n; ++i) f[i][i] = 0;
    for (int i = 1; i < n; ++i) {
        for (int j = 1; j <= n - i; ++j) {
            for (int k = j; k < j + i; ++k) {
                f[j][j + i] = min(f[j][j + i], f[j][k] + f[k + 1][j + i] + s[j + i] - s[j - 1]);
            }
        }
    }
    int ans = 1 << 30;
    for (int i = 1; i <= n/2; ++i)
        ans = min(ans, f[i][i + n/2 - 1]);
    printf("%d\n", ans);
    return 0;
}
括号序列
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
  int x = 0;
  bool f = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f |= (c == '-');
  for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return f ? -x : x;
}

int f[507][507];
char s[507];

int main() {
    int n = rd();
    scanf("%s", s + 1);
    memset(f, 0, sizeof(f));
    for (int i = 1; i < n; ++i) {
        for (int j = 1; j <= n - i; ++j) {
            if ((s[j] == '(' && s[j + i] == ')') || (s[j] == '[' && s[j + i] == ']'))
                f[j][j + i] = f[j + 1][j + i - 1] + 2;
            for (int k = j; k < j + i; ++k)
                f[j][j + i] = max(f[j][j + i], f[j][k] + f[k + 1][j + i]);
        }
    }
    printf("%d\n", f[1][n]);
    return 0;
}

树型DP

统计人数

一家公司里有 ​ 个员工，除了公司 CEO 外，每个人都有一个直接上司。我们想知道，每个人的团队（包括他/她自己、他的直接下属和间接下属）一共有多少人

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
  int x = 0;
  bool f = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f |= (c == '-');
  for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return f ? -x : x;
}

struct node {
    node *nxt;
    int where;
} *first[100001], a[100001];

int n, l, f[100001];

inline void makelist(int x, int y) {
    a[++l].where = y;
    a[l].nxt = first[x];
    first[x] = &a[l];
}

inline void solve(int i) {
    f[i] = 1;
    for (node *x = first[i]; x; x = x -> nxt) {
        solve(x -> where);
        f[i] += f[x -> where];
    }
}

int main() {
    n = rd();
    memset(first, 0, sizeof(first));
    l = 0;
    for (int i = 2; i <= n; ++i) {
        int x;
        scanf("%d", &x);
        makelist(x, i);
    }
    solve(1);
    for (int i = 1; i <= n; ++i ){
        printf("%d ", f[i]);
    }
    return 0;
}
没有上司的舞会

一家公司里有 个员工，除了公司 CEO 外，每个人都有一个直接上司。今天公司要办一个舞会，为了大家玩得尽兴，如果某个员工的直接上司来了，他/她就不想来了。第 个员工来参加舞会会为大家带来 ​ 点快乐值。请求出快乐值最大是多少。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
  int x = 0;
  bool f = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f |= (c == '-');
  for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return f ? -x : x;
}

struct node {
    node *nxt;
    int where;
} *first[100001], a[100001];

int n, l, v[100001];
ll f[100001][2];

inline void makelist(int x, int y) {
    a[++l].where = y;
    a[l].nxt = first[x];
    first[x] = &a[l];
}

inline void solve(int i) {
    f[i][1] = v[i];
    for (node *x = first[i]; x; x = x -> nxt) {
        solve(x -> where);
        f[i][0] += max(f[x -> where][0], f[x -> where][1]);
        f[i][1] += f[x -> where][0];
    }
}

int main() {
    n = rd();
    memset(first, 0, sizeof(first));
    l = 0;
    for (int i = 2; i <= n; ++i) {
        int x;
        scanf("%d", &x);
        makelist(x, i);
    }
    for (int i = 1; i <= n; ++i) {
        v[i] = rd();
    }
    solve(1);
    printf("%lld\n", max(f[1][0], f[1][1]));
    return 0;
}
没有上司的舞会2

一家公司里有 个员工，除了公司 CEO 外，每个人都有一个直接上司。今天公司要办一个舞会，为了大家玩得尽兴，如果某个员工的直接上司来了，他/她就不想来了。第 个员工来参加舞会会为大家带来 点快乐值。由于场地有大小限制，场地最多只能容纳 个人。请求出快乐值最大是多少。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
  int x = 0;
  bool f = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f |= (c == '-');
  for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return f ? -x : x;
}

struct node {
    node *nxt;
    int where;
} *first[100001], a[100001];

int n, m, l, v[501];
ll f[501][501][2];

inline void makelist(int x, int y) {
    a[++l].where = y;
    a[l].nxt = first[x];
    first[x] = &a[l];
}

inline void solve(int i) {
    for (node *x = first[i]; x; x = x -> nxt) {
        solve(x -> where);
        for (int j = m; j >= 0; --j)
            for (int k = 0; k <= j; ++k) {
                f[i][j][0] = max(f[i][j][0], f[i][j - k][0] + max(f[x -> where][k][0], f[x -> where][k][1]));
                f[i][j][1] = max(f[i][j][1], f[i][j - k][1] + f[x -> where][k][0]);
            }
    }
    for (int j = m; j; --j)
        f[i][j][1] = f[i][j - 1][1] + v[i];
    f[i][0][1] = 0;
}

int main() {
    n = rd(); m = rd();
    memset(first, 0, sizeof(first));
    l = 0;
    for (int i = 2; i <= n; ++i) {
        int x;
        scanf("%d", &x);
        makelist(x, i);
    }
    for (int i = 1; i <= n; ++i) {
        v[i] = rd();
    }
    solve(1);
    printf("%lld\n", max(f[1][m][0], f[1][m][1]));
    return 0;
}
  • Post title：区间DP && 树形DP
  • Post author：Eva.Q
  • Create time：2022-01-26 10:19:07
  • Post link：https://qyy/2022/01/26/Algorithm/DP2/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.