区间、计数、数位统计、状态压缩、树形等DP问题

区间DP

AcWing 282. 石子合并

计数类DP

AcWing 900. 整数划分

数位统计DP

AcWing 338. 计数问题

数字 1 11 21 31 41 51 61 71 81 91 101 111 231 991
ans 1 2 3 4 5 6 7 8 9 10 11 12 24 100

发现一个规律：假设x的每一位分别为abcdefg，那么当g == 1时，我们的答案就是abcdef + 1

假如g < 1的，那最后就不会统计到abcdef1这个数字，答案就是abcdefg

如果g > 1，那么答案也是abcdef + 1

所以统计个位数的规律我们可以视为 n/10+(n%10>=1)

x 100 200 300 1000 1600 161a(9=>a>=0) 1650
n 10 20 30 100 160 160+(a+1) 160+10 
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
#include <bits/stdc++.h>

using namespace std;

const int N = 10;

// 将num数组存的数合成一个整树 
int get(vector<int> num, int l, int r)
{
    int res = 0;
    for (int i = l; i >= r; i -- )
        res = res * 10 + num[i];
    return res;
}

int power10(int x)
{
    int res = 1;
    while (x -- ) res *= 10;
    return res;
}

int count(int n, int x)
{
    if (!n) return 0;
    
    vector<int> num;
    while (n)
    {
        num.push_back(n % 10);
        n /= 10;
    }
    n = num.size();
    int res = 0;
    
    for (int i = n - 1 - !x; i >= 0; i -- )
    {
        if (i < n - 1)
        {
            res += get(num, n - 1, i + 1) * power10(i);
            if (!x) res -= power10(i);
        }
        if (num[i] == x) res += get(num, i - 1, 0) + 1;
        else if (num[i] > x) res += power10(i);
    }
    return res;
}

int main()
{
    int a, b;
    while (cin >> a >> b, a)
    {
        if (a > b) swap(a, b); // 从小到大
        
        for (int i = 0; i <= 9; i ++ )
            cout << count(b, i) - count(a - 1, i) << ' ';
        cout << endl;
    }
    
    return 0;
}

这个使用了类似前缀和的方式 ，求a-b之间的数字，我们找到计算的规律后，直接用(0,b)-(0,a- 1)的，就得到答案了

状态压缩DP

AcWing 291. 蒙德里安的梦想

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
// 朴素版的写法
#include <bits/stdc++.h>

using namespace std;

const int N = 12, M = 1 << N;

int n, m;
long long f[N][M];  //  f[i][j]表示处理到第i列且状态为j时的方案数
bool st[M];

// (j&k) == 0   两列的状态不能有重叠
//两列的并集  (j | k) 不存在连续奇数个0

int main()
{
    while (cin >> n >> m, n || m)  // 循环读取输入，当n和m不同时为0时继续
    {
        for (int i = 0; i < 1 << n; i ++ )
        {
            int cnt = 0;
            st[i] = true; // 初始假设状态i合法
            for (int j = 0; j < n; j ++ )   // 检查状态i的每一位（从低位到高位）
                if (i >> j & 1)  // 检查第j位是否为1
                { // 如果是1，检查之前连续0的个数是否为奇数（cnt & 1），若是则状态不合法
                    if (cnt & 1) st[i] = false;
                    cnt = 0;  // 重置计数器cnt = 0
                }
                else cnt ++ ;
            if (cnt & 1) st[i] = false;
        }
        memset(f, 0, sizeof f);
        f[0][0] = 1;
        for (int i = 1; i <= m; i ++)  // 遍历每一列i（从1到m）
            for (int j = 0; j < 1 << n; j ++ )  // 枚举当前列i的所有可能状态j
                for (int k = 0; k < 1 << n; k ++ ) // 枚举前一列i-1的所有可能状态k
                    if ((j & k) == 0 && st[j | k]) 
                        f[i][j] += f[i - 1][k];
        cout << f[m][0] << endl;
    }
    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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
// 去除无效状态的优化写法
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 12, M = 1 << N;

int n, m;
LL f[N][M];
vector<int> state[M];
bool st[M];  // state[i]存储所有能与状态i相邻的合法状态(所有能转移到状态i的合法状态)

int main()
{
    while (cin >> n >> m, n || m)
    {
        for (int i = 0; i < 1 << n; i ++ )
        {
            int cnt = 0;  // 记录当前连续的空位数量
            bool is_valid = true;
            for (int j = 0; j < n; j ++ )
                if (i >> j & 1)  // 用于检查整数 i 的第 j 位（从右往左数，最低位为第0位）是否为1。
                {
                    if (cnt & 1) // 如果之前的空位数是奇数，无法放满竖方块
                    {
                        is_valid = false;
                        break;
                    }
                }
            	else cnt ++ ;  // 如果第j行是空的，计数器加1
            if (cnt & 1) is_valid = false;  // 检查最后一组连续空位，如果是奇数则不合法
            st[i] = is_valid;  // 记录状态i的合法性
        }
        
        for (int i = 0; i < 1 << n; i ++ )    // 遍历所有可能的状态
        {
            // 清空上一次计算的结果
            // 如果不清空，当处理第二组输入时：
            // state[i]中会同时包含上一组输入的状态和新输入的状态
            // 例如，第一次n=3时计算的状态和第二次n=4时计算的状态会混在一起，导致错误
            state[i].clear();
            for (int j = 0; j < 1 << n; j ++ )
                if ((i & j) == 0 && st[i | j])
                    state[i].push_back(j);
        }
        memset(f, 0, sizeof f);
        f[0][0] = 1;
        for (int i = 1; i <= m; i ++ )
            for (int j = 0; j < 1 << n; j ++ )
                for (auto k : state[j])
                    f[i][j] += f[i - 1][k];  // 累加所有可能的转移方案数
        
        cout << f[m][0] << endl; // 输出最终结果：第m列状态为0(第0~m-1列全部填满且没有伸出)的方案数
    }
    return 0;
}

AcWing 91. 最短Hamilton路径

树形DP

AcWing 285. 没有上司的舞会

记忆化搜索

AcWing 901. 滑雪