AcWing 算法提高第一章动态规划

树形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
42
43
44
45


#include <bits/stdc++.h>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const int N = 1e4 + 5, M = 2 * N;

int n, tot, ans;
int ver[M], edge[M], nxt[M], head[N];

void add(int x, int y, int z) {
    ver[++tot] = y, edge[tot] = z, nxt[tot] = head[x], head[x] = tot;
}

int dfs(int x, int fa) {
    int maxd = 0; // 从当前点向下最大长度
    int d1 = 0, d2 = 0;
    for (int i = head[x]; i; i = nxt[i]) {
        int y = ver[i];
        if (y == fa) continue;
        int dis = dfs(y, x) + edge[i];
        maxd = max(maxd, dis);
        if (dis >= d1) d2 = d1, d1 = dis;
        else if (dis > d2) d2 = dis; 
    }
    ans = max(ans, d1 + d2);
    return maxd;
}

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z); add(y, x, z);
    }
    dfs(1, -1);
    cout << ans << '\n';
    return 0;
}

1073. 树的中心

题意：一棵包含 $n$ 个结点和 $n-1$ 条无向边，每条边都有一个权值，在树中找到一点，使得该点到树中其他结点的最远距离最近，输出所求点到树中其他结点的最远距离。

求出每个点到其他点的最长距离，输出最短的一个，做两次 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
48
49
50
51
52
53
54
55
56
57
58
59


#include <bits/stdc++.h>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const int N = 1e4 + 5, M = N << 1;

int n, tot;
int head[N], ver[M], edge[M], nxt[M];
int d1[N], d2[N], up[N], p[N];

void add(int x, int y, int z) {
	ver[++tot] = y, edge[tot] = z, nxt[tot] = head[x], head[x] = tot;
}

int dfs1(int x, int fa) {
	d1[x] = d2[x] = -INF;
	for (int i = head[x]; i; i = nxt[i]) {
		int y = ver[i];
		if (y == fa) continue;
		int d = dfs1(y, x) + edge[i];
		if (d >= d1[x]) d2[x] = d1[x], d1[x] = d, p[x] = y;
		else if (d > d2[x]) d2[x] = d;
	}
	if (d1[x] == -INF) d1[x] = d2[x] = 0;
	return d1[x];
}

void dfs2(int x, int fa) {
	for (int i = head[x]; i; i = nxt[i]) {
		int y = ver[i];
		if (y == fa) continue;
		if (p[x] == y) up[y] = max(up[x], d2[x]) + edge[i];
		else up[y] = max(up[x], d1[x]) + edge[i];
		dfs2(y, x);
	}
}

int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	int x, y, z;
	for (int i = 1; i < n; ++i) {
		cin >> x >> y >> z;
		add(x, y, z); add(y, x, z);
	}
	dfs1(1, -1);
	dfs2(1, -1);
	int ans = d1[1];
	for (int i = 2; i <= n; ++i) {
		ans = min(ans, max(d1[i], up[i]));
	}
	cout << ans << '\n';
    return 0;
}

1075. 数字转换

 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 <bits/stdc++.h>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const int N = 5e4 + 5;

int n, tot, ans;
int ver[N], nxt[N], head[N];
int sum[N], st[N];

void add(int x, int y) {
	ver[++tot] = y, nxt[tot] = head[x], head[x] = tot;
}

int dfs(int x) {
	int d1 = 0, d2 = 0;
	for (int i = head[x]; i; i = nxt[i]) {
		int y = ver[i];
		int d = dfs(y) + 1;
		if (d >= d1) d2 = d1, d1 = d;
		else if (d > d2) d2 = d;
	}
	ans = max(ans, d1 + d2);
	return d1;
}

int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		for (int j = i * 2; j <= n; j += i) {
			sum[j] += i;
		}
	}
	for (int i = 2; i <= n; ++i) {
		if (i > sum[i]) {
			add(sum[i], i);
			st[i] = 1;
		}
	}
	for (int i = 1; i <= n; ++i) {
		if (!st[i]) dfs(i);
	}
	cout << ans << '\n';
    return 0;
}

数位DP

1081. 度的数量

题意：求给定区间 $[X,Y]$ 中满足下列条件的整数个数：这个数恰好等于 $K$ 个互不相等的 $B$ 的整数次幂之和。

所求转化成求$dp(y)-dp(x-1)$的形式，$dp(x)$表示区间 $[0,x]$ 的个数，条件即 B 进制 K 个 1 的情况。

 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 <bits/stdc++.h>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const int N = 35;

int x, y, k, b;
int C[N][N];

int dp(int x) {
    if (!x) return 0;
    vector<int> num;
    while (x) num.push_back(x % b), x /= b;
    int res = 0, last = 0;
    for (int i = num.size() - 1; i >= 0; --i) {
        int t = num[i];
        if (t) {
            res += C[i][k-last];
            if (t > 1) {
                if (k >= last + 1) res += C[i][k-last-1];
                break;
            }
            else {
                last++;
                if (last > k) break;
            }
        }
        if (!i && last == k) res++;
    }
    return res;
}

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> x >> y >> k >> b;
    for (int i = 0; i <= N; ++i) {
        C[i][0] = 1;
        for (int j = 1; j <= i; ++j) C[i][j] = C[i-1][j] + C[i-1][j-1];
    }
    cout << dp(y) - dp(x - 1) << '\n';
    return 0;
}

1082. 数字游戏

题意：求区间 $[a,b]$ 内的不降数个数。

用 $f[i][j]$ 表示 $i$ 位数且最高位为 $j$ 的不降数的方案数，则 $f[i][j]=\sum_{k=j}^9f[i-1][k]$。

 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


#include <bits/stdc++.h>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const int N = 11;

int a, b;
int f[N][10];

void init() {
    for (int i = 0; i <= 9; ++i) f[1][i]= 1;
    for (int i = 2; i < N; ++i) {
        for (int j = 0; j <= 9; ++j) {
            for (int k = j; k <= 9; ++k) {
                f[i][j] += f[i-1][k];
            }
        }
    }
}

int dp(int x) {
    if (!x) return 1;
    vector<int> num;
    while (x) num.push_back(x % 10), x /= 10;
    int res = 0, last = 0;
    for (int i = num.size() - 1; i >= 0; --i) {
        int t = num[i];
        for (int j = last; j < t; ++j) {
            res += f[i+1][j];
        }
        if (t < last) break;
        last = t;
        if (!i) res++; // 该数合法
    }
    return res;
}

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    init();
    while (cin >> a >> b) {
        cout << dp(b) - dp(a-1) << '\n';
    }
    return 0;
}

1083. Windy数

题意：求区间 $[a,b]$ 内的 Windy 数，Windy 数指：不含前导 0 且相邻两个数字之差至少为 2 的正整数。

用 $f[i][j]$ 表示 $i$ 位数且最高位为 $j$ 的 Windy 数个数，则 $f[i][j]=\sum_{|j-k|\ge2}f[i-1][k]$。

 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


#include <bits/stdc++.h>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const int N = 11;

int a, b;
int f[N][10];

void init() {
    for (int i = 0; i <= 9; ++i) f[1][i] = 1;
    for (int i = 2; i < N; ++i) {
        for (int j = 0; j <= 9; ++j) {
            for (int k = 0; k <= 9; ++k) {
                if (abs(j - k) >= 2) f[i][j] += f[i-1][k];	
             }
        }
    }
}

int dp(int x) {
    if (!x) return 0;
    vector<int> num;
    while (x) num.push_back(x % 10), x /= 10;
    int res = 0, last = -2;
    for (int i = num.size() - 1; i >= 0; --i) {
        int t = num[i];
        for (int j = (i == (int)num.size() - 1); j < t; ++j) {
            if (abs(j - last) >= 2) res += f[i+1][j];
        }
        if (abs(t - last) < 2) break;
        last = t;
        if (!i) res++;
    }
    // 有前导 0 的情况
    for (int i = 1; i < (int)num.size(); ++i) {
        for (int j = 1; j <= 9; ++j) {
            res += f[i][j];
        }
    }
    return res;
}

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    init();
    cin >> a >> b;
    cout << dp(b) - dp(a - 1) << '\n';
    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
32
33
34
35
36
37
38
39
40


#include <bits/stdc++.h>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const int N = 11;

int l, r, len;
int dp[N][10], a[11];

int dfs(int cur, int last, int st, int lim) { // st 是否含前导 0
    if (!cur) return 1;
    if (!lim && ~dp[cur][last]) return dp[cur][last];
    int res = 0, up = lim ? a[cur] : 9;
    for (int i = 0; i <= up; ++i) {
        if (abs(i - last) < 2) continue;
        if(st && !i) res += dfs(cur - 1, -2, 1, lim && i == up);
        else res += dfs(cur - 1, i, 0, lim && i == up);
    }
    if (!lim && !st) dp[cur][last] = res;
    return res;
}

int part(int x) {
    len = 0;
    while (x) a[++len] = x % 10, x /= 10;
    memset(dp, -1, sizeof dp);
    return dfs(len, -2, 1, 1);
}

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> l >> r;
    cout << part(r) - part(l - 1) << '\n';
    return 0;
}

1084. 数字游戏 II

题意：求区间 $[a,b]$ 内的模数个数，模数指：各位数字之和 $\mod N$ 为 $0$。

用 $f[i][j][k]$ 表示 $i$ 位数且最高位为 $j$ 所有数字和 $\mod N$ 为 $k$ 的数的个数，则 $f[i][j][k]=\sum_{x=0}^9f[i-1][x][((k-j)%N+N)%N]$。

 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


#include <bits/stdc++.h>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const int N = 11, M = 105;

int a, b, p;
int f[N][10][M];

int mod(int x, int y) {
    return ((x % y) + y) % y;
}

void init() {
    memset(f, 0, sizeof(f));
    for (int i = 0; i <= 9; ++i) f[1][i][i%p] = 1;
    for (int i = 2; i < N; ++i) {
        for (int j = 0; j <= 9; ++j) {
            for (int k = 0; k < p; ++k) {
                for (int x = 0; x <= 9; ++x) {
                    f[i][j][k] += f[i-1][x][mod(k-j,p)];
                }
            }
        }
    }
}

int dp(int x) {
    if (!x) return 1;
    vector<int> num;
    while (x) num.push_back(x % 10), x /= 10;
    int res = 0, last = 0;
    for (int i = num.size() - 1; i >= 0; --i) {
        int t = num[i];
        for (int j = 0; j < t; ++j) {
            res += f[i+1][j][mod(-last, p)];
        }
        last += t;
        if (!i && last % p == 0) res++;
    }
    return res;
}

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    while(cin >> a >> b >> p) {
        init();
        cout << dp(b) - dp(a - 1) << '\n';
    }
    return 0;
}

1085. 不要62

题意：求区间 $[a,b]$ 内不含 4 和 62 的数的个数。

用 $f[i][j]$ 表示 $i$ 位数且最高位为 $j$ 满足条件的数的个数。

 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


#include <bits/stdc++.h>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const int N = 11;

int n, m;
int f[N][10];

void init() {
    for (int i = 0; i <= 9; ++i) f[1][i] = 1;
    f[1][4] = 0;
    for (int i = 2; i < N; ++i) {
        for (int j = 0; j <= 9; ++j) {
            if (j == 4) continue;
            for (int k = 0; k <= 9; ++k) {
                if (k == 4 || (j == 6 && k == 2)) continue;
                f[i][j] += f[i-1][k];
            }
        }
    }
}

int dp(int x) {
    if (!x) return 1;
    vector<int> num;
    while (x) num.push_back(x % 10), x /= 10;
    int res = 0, last = 0;
    for (int i = num.size() - 1; i >= 0; --i) {
        int t = num[i];
        for (int j = 0; j < t; ++j) {
            if (j == 4 || (last == 6 && j == 2)) continue;
            res += f[i+1][j];
        }
        if (t == 4 || (last == 6 && t == 2)) break;
        last = t;
        if (!i) res++;
    }
    return res;
}

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    init();
    while (cin >> n >> m && (n + m)) {
        cout << dp(m) - dp(n - 1) << '\n';
    }
    return 0;
}

Contents

树形DP

数位DP