状态机模型

对于状态机而言，如果上一个状态合法，而且可以转移到当前状态，那么这个转移合法。状态机的转移，就类似于图中两个点连边。主要是判断这个转移是否合法， 如果合法，就添加边。

以没有上司的舞会这题为例，当前上司不参加对应两种状态：其下属参加和下属不参加都是合法的。当前上次参加对应两种状态：其下属参加和下属不参加，那么第一种状态就是非法的。

题目： 街道上有 nn 家店铺，第 ii 家店铺的财产是 a[i]a[i] 。小偷不能连续偷两个相邻的店铺。求小偷能获得的最大财产。

如果要偷第 ii 家店铺，那么第 i−1i-1 个店铺不能被偷，因为这是非法的，此时

dp[1][i]=max(dp[1][i−2],dp[0])+a[i]dp[1][i] = max(dp[1][i - 2], dp[0]) + a[i]

否则的话

dp[0][i]=max(dp[1][i−1],dp[0][i−1])dp[0][i] = max(dp[1][i - 1], dp[0][i - 1])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ll n;
ll a[MAXN];
ll dp[2][MAXN]; //1表示抢劫i，0表示不抢劫i
void solve() {
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    dp[0][0] = 0; dp[1][0] = 0;
    dp[0][1] = 0, dp[1][1] = a[1];
    for (int i = 2; i <= n; i++) {
        dp[0][i] = max(dp[1][i - 1], dp[0][i - 1]);
        dp[1][i] = max(dp[0][i - 1] + a[i], dp[1][i - 2] + a[i]);
    }
    printf("%lld\n", max(dp[0][n], dp[1][n]));
}

题目： 给定一个长度为 nn 的数组，数组中的第 ii 个数字表示一个给定股票在第 ii 天的价格。最多可以完成 kk 笔交易，计算所能获取的最大利润。一次买入一次卖出即为一笔交易，且不能同时产生多笔交易。

定义状态 dp[i][j][k]dp[i][j][k] 表示前 ii 天，进行了 kk 笔交易，状态jj 为 00 （空仓）或状态 jj 为 11 （持仓）时的最多利润。

若当前这一天空仓，要么前一天也空仓，要么当前这一天把股票卖出了（此时注意交易数需要减一）

若当前这一天持仓，要么前一天也持仓，要么当前这一天买入了股票

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
ll n, k;
ll a[MAXN];
ll dp[2][2][105]; //前i天，交易k次，状态为 0（空仓）1（持仓）
void solve() {
    n = read(), k = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    memset(dp, ~0x3f, sizeof dp); //交易一次以上的赋为负无穷
    for (int i = 0; i <= n; i++) dp[i][0][0] = 0; //没有交易过的赋为0
    dp[0][0][0] = 0;
    for (int i = 1; i <= n; i++) {
        int now = i & 1;
        int pre = 1 - now;
        for (int j = 0; j <= k; j++) {
            //若持仓，要么前一天也持仓，要么当前这一天买入股票
            dp[now][1][j] = max(dp[pre][1][j], dp[pre][0][j] - a[i]);
            //若空仓，要么前一天也空仓，要么当前这一天卖出股票
            if (!j) 
                dp[now][0][j] = 0;
            else
                dp[now][0][j] = max(dp[pre][0][j], dp[pre][1][j - 1] + a[i]);
        }
    }
    ll ans = -INF;
    for (int i = 0; i <= k; i++) ans = max(ans, dp[i & 1][0][i]);
    printf("%lld\n", ans);
}

同样，修改条件。去掉了交易次数的限制，但是新增了一个状态：冷冻期。在卖出股票后进入一天冷冻期，在这期间内不能买入股票。

状态机图示：

image-20220717193748940

空仓时，要么前一天也空仓，要么前两天卖出即前一天是冷冻期。

持仓时，要么前一天也持仓，要么前一天空仓当前买入

冷冻期时，前一天持仓前一天卖出

最后一天要么是空仓状态要么是冷冻期，比较一下取最大即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
ll dp[2][3];
ll n;
ll a[MAXN];
void solve() {
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    //空仓，0，要么前一天空仓，要么前两天卖出即前一天冷冻
    //持仓, 1，要么前一天持仓，要么前一天空仓后当前买入
    //冷冻，2，前一天持仓前一天卖出
    dp[0][1] = -INF, dp[0][2] = -INF; //非法状态
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        int now = i & 1;
        int pre = 1 - now;
        dp[now][0] = max(dp[pre][0], dp[pre][2]);
        dp[now][1] = max(dp[pre][1], dp[pre][0] - a[i]);
        dp[now][2] = dp[pre][1] + a[i];
    }
    printf("%lld\n", max(dp[n & 1][0], dp[n & 1][2]));
}

**题目：**给定一个长度为 mm 的字符串T和一个整数 nn ，现需设计一个密码SS满足 SS 仅有长度为 nn 的小写字母组成且 SS 不包含子串 TT 。问有几种方案。

只有密码的最大后缀子串为 mm 时方案才不合法，也就是说最大后缀子串长度小于 mm 时都是合法方案。定义 dp[i][j]dp[i][j] 表示构造一个长度为 ii 的密码，且后缀与模式串匹配的最大长度为 jj 的方案数量。根据上面的结论，可以得出 ans=∑dp[n][j],0≤j<mans = \sum{dp[n][j], 0 \leq j < m} 。可以证明这是不重不漏的。这时一共有 m+1m+1 个状态，其中最后一个状态即匹配长度为 mm 的状态为非法状态。

状态机大概长这样

image-20220717193759100

1
2
3
4
5
6
7
8
9
10
11
12
// kmp匹配过程
    for(int i=1,j=0;i<=m;i++)
    {
        while(j && s[i] != p[j+1]) j = ne[j]; //如果不能j往前走，就退一步
        if(s[i] == p[j+1]) j++;
        if(j == n)
        {
            // 匹配成功
            printf("%d ",i-n);
            j = ne[j]; 
        }
    }

若下一个字母能直接匹配上，那么 dp[i+1][j+1]+=dp[i][j]dp[i+1][j+1] += dp[i][j]

若下一个字母不能匹配上，跳到了 pos=nxt[j]pos = nxt[j] 。如果 T[pos+1]=chT[pos +1] = ch ，那么 dp[i+1][len]+=dp[i][j]dp[i+1][len]+=dp[i][j] ，lenlen 表示匹配的长度。

若 nxt[j]≠posnxt[j] \neq pos ，表示匹配不上，即匹配长度为 00 。那么，dp[i+1][0]+=dp[i][j]dp[i +1][0] += dp[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
char s[MAXN]; //模式串
int n;
int nxt[MAXN];
ll dp[MAXN][MAXN];
void solve() {
    n = read();
    scanf("%s", s + 1);
    int m = strlen(s + 1);
    for (int i = 2, j = 0; i <= m; i++) { //求kmp的next数组
        while (j && s[i] != s[j + 1]) j = nxt[j];
        if (s[i] == s[j + 1]) j++;
        nxt[i] = j;
    }
    dp[0][0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) { //枚举匹配的最大后缀
            for (char ch = 'a'; ch <= 'z'; ch++) {
                int len = j; //计算枚举到第i+1个字符后，后缀匹配的最大长度
                while (len && s[len + 1] != ch) len = nxt[len];
                if (s[len + 1] == ch) len++; //能够匹配上
                if (!len) //第i+1为ch时，不能匹配上
                    dp[i + 1][0] = (dp[i + 1][0] + dp[i][j]) % mod;
                else //第i+1为ch时，能够匹配上，那么最大长度加1
                    dp[i + 1][len] = (dp[i + 1][len] + dp[i][j]) % mod;
            }
        }
    }
    ll ans = 0;
    for (int i = 0; i < m; i++) ans = (ans + dp[n][i]) % mod;
    printf("%lld\n", ans);
}

状态压缩模型

大体分两种，棋盘式（在棋盘上放棋子避免他们互相攻击，判断连通性），集合式（每个元素在不在集合里面）。核心就是用一串二进制数暴力压缩掉一维的数。

棋盘类

题目：

在 n×nn \times n 的棋盘上放 kk 个国王。国王可攻击相邻的 88 个格子，求使得这 kk 棋子无法互相攻击的方案总数。

用长度为 nn 的二进制数来表示一行的状态。这样当 (st>>i)=1(st >> i) = 1 时，即表示当前这位上存在棋子，否则不存在。这样就可以预处理出单独一行的所有合法状态和两行之间的所有合法状态。定义 dp[i][k][j]dp[i][k][j] 为第 ii 行，放置了 kk 个国王，当前行状态为 jj 时的方案数量。初始化 dp[0][0][0]=1dp[0][0][0]=1

转移方程： dp[i][k][j]=∑dp[i−1][k−cnt[j]][pre]dp[i][k][j] = \sum{dp[i - 1][k - cnt[j]][pre]} ，prepre 表示上一行的合法状态。

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
int n, m;
ll dp[2][105][(1 << MAXN) + 5];
int cnt[(1 << MAXN)];
vector<int> v; //存储当前行的合法状态
vector<int> g[(1 << MAXN) + 5]; //存储行与行之间的合法状态
bool judge(int st) { //行内判断合法状态
    if (st & st << 1) return false;
    if (st & st >> 1) return false;
    return true;
}

bool work(int now, int pre) { //行与行之间判断合法状态
    if (now & pre) return false;
    if (now & pre >> 1) return false;
    if (now & pre << 1) return false;
    return true;
}

int sum(int st) {
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int u = st >> i & 1;
        ans += u;
    }
    return ans;
}

void solve() {
    n = read(), m = read();
    vector<int> v;
    for (int st = 0; st < (1 << n); st++) 
        if (judge(st))
            v.pb(st), cnt[st] = sum(st);
    for (int now : v) 
        for (int pre : v)
            if (work(now, pre))
                g[now].pb(pre);
    dp[0][0][0] = 1;
    for (int i = 1; i <= n; i++) 
        for (int k = 0; k <= m; k++) 
            for (int now : v) {
                dp[i & 1][k][now] = 0; //先清零因为是+=，滚动数组之前的结果有影响
                for (int pre : g[now]) 
                    if (cnt[now] <= k)
                        dp[i & 1][k][now] += dp[(i - 1) & 1][k - cnt[now]][pre];           
            }
    ll ans = 0;            
    for (int st : v) ans += dp[n & 1][m][st];
    printf("%lld\n", ans);
}

题目： 给定一个 n×mn \times m 的矩阵，矩阵中 HH 表示不能放置棋子，标 PP 表示可以放置棋子。棋子的攻击方向为上下左右，距离两个单位。求出最大的棋子放置数量，使得棋子之间不会互相攻击。

加入了图的限制。不过可以用类似的方式，把矩阵每一层的状态也用二进制来压缩存储，注意：用0表示该位置能放棋子，1表示不能放 。这样只需要把当前这一层的状态 stst 和矩阵这一层的状态做与运算。如果结果为 00 ，表示合法；若为 11 ，说明放置棋子的位置与不能放置棋子的位置发生重叠，该状态非法。然后可以发现，与之前的 workwork 函数所表示的含义是一样的，于是乎就可以共用了。

若只压缩一层的信息，只能保证上一层是合法的，不能保证上上层摆放的棋子一定攻击不到当前这层。所以状态定义的时候多加一位，然后通过预处理的邻接矩阵枚举合法的第 i−2i - 2 层状态进行转移即可。

  • 状态表示 dp[i][j][k]dp[i][j][k] ：考虑前 ii 层且第 ii 层状态为 jj ，第 i−1i-1 层状态为 kk 的方案。
  • 状态属性：该方案能够放置棋子的最大个数
  • 状态计算： dp[i][j][k]=maxdp[i][j][k] = max {dp[i−1][k][pre]dp[i - 1][k][pre]} + cnt[j]cnt[j] ，prepre 表示能够与 kk 和 jj 同时合法存在于三行中的所有状态
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
char s[105][15];
int a[105];
int n, m;
vector<int> v;
vector<int> g[(1 << 10) + 5];
int cnt[(1 << 10) + 5];
ll dp[2][(1 << 10) + 5][(1 << 10) + 5];
bool judge(int st) {
    if (st & (st >> 1) || st & (st >> 2)) return false;
    if (st & (st << 1) || st & (st << 2)) return false;
    return true; 
}

bool work(int now, int pre) {
    if (now & pre) return false;
    return true;
}

int sum(int st) {
    int ans = 0;
    for (int i = 0; i < m; i++) {
        int u = st >> i & 1;
        ans += u;
    }
    return ans;
}

void solve() {
    n = read(), m = read();
    for (int i = 1; i <= n; i++)
        scanf("%s", s[i]);
    for (int i = 1; i <= n; i++) {
        int ans = 0;
        for (int j = 0; j < m; j++) {
            if (s[i][j] == 'P') //山地
                {}
            else //平原
                ans += (1 << j);
        }
        a[i] = ans;
    }
    for (int st = 0; st < (1 << m); st++) 
        if (judge(st)) 
            v.pb(st), cnt[st] = sum(st);
    for (int now : v) 
        for (int pre : v)
            if (work(now, pre))
                g[now].pb(pre);
    for (int i = 1; i <= n; i++) 
        for (int now : v) 
            for (int PRE : g[now]) {
                dp[i & 1][now][PRE] = 0; //清空滚动数组之前的结果
                if (work(now, a[i])) //当前行合法
                    for (int pre : g[PRE]) //枚举上上行
                        if (work(now, pre)) //若上上行和当前和不会互相攻击
                            dp[i & 1][now][PRE] = max(dp[i & 1][now][PRE], dp[(i - 1) & 1][PRE][pre] + cnt[now]);
            }          
    ll ans = 0;
    for (int now : v) 
        for (int pre : g[now]) 
            ans = max(ans, dp[n & 1][now][pre]);   
    printf("%lld\n", ans);
}

上面只管了当前这一行与图的合法关系。因为之前行若与图之间不合法的话，最大值一定为 00 （因为有个 ifif 来判断），对答案无影响。如果是算方案数类型的题目也没影响，因为一开始会对所有的状态清零，若某一状态与图之间的关系非法，那么该状态的方案数也一定为 00 ，对答案也没有影响。代码写起来长这样：

1
2
3
4
5
6
7
8
dp[0][0] = 1;
for (int i = 1; i <= n; i++) 
    for (int now : v) {
        dp[i & 1][now] = 0;
        if (work(now, a[i])) 
            for (int pre : g[now]) 
                dp[i & 1][now] = (dp[i & 1][now] + dp[(i - 1) & 1][pre]) % mod;
    }

更加易懂（但是慢）的代码：

1
2
3
4
5
6
7
8
9
10
11
for (int i = 1; i <= n; i++)
    for (int j = 0; j < state.size(); j++)
        for (int k = 0; k < state.size(); k++)
            for (int u = 0; u < state.size(); u++) {
                int a = state[j], b = state[k], c = state[u];
                if (a & b | a & c | b & c) //能互相攻击
                    continue;
                if (g[i] & b | g[i - 1] & a) //在不该放置棋子的地方放了棋子
                    continue;
                f[i & 1][j][k] = max(f[i & 1][j][k], f[i - 1 & 1][u][j] + cnt[b]);
            }

集合类

题意： 愤怒的小鸟模型。给出 nn 个猪的坐标，问最少几条抛物线能把猪全部打死（抛物线开口向下，且一定从坐标原点开始）

根据简单数学知识，在本题中，两头猪确定一条抛物线，所以最多有 n2n^2 条抛物线。

预处理 seg[i][j]seg[i][j] 数组，表示编号为 ii 的猪和编号为 jj 的猪所在的抛物线。属性表示为这个抛物线可消灭的猪的编号，二进制表示。如100111，表示 1,2,3,61,2,3,6 的猪能被当前这条抛物线杀死。

状态表示 dp[i]dp[i] ，ii 这个状态（二进制表示）下最少要用多少条抛物线击杀所有猪。属性为最小值。

状态计算：找到 ii 状态下没有被消灭的猪的其中一个编号 xx ，枚举可消灭它的抛物线 seg[x][j]seg[x][j] 并更新状态。

dp[i∣seg[x][j]]=min(dp[i∣seg[x][j]],dp[i]+1)dp[i|seg[x][j]] = min(dp[i | seg[x][j]], dp[i] +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
int seg[MAXN][MAXN]; //所有抛物线杀死猪的情况，1表示被杀死
pdd node[MAXN];
ll dp[1 << MAXN];
int n, m;

int cmp(double a, double b) {
    if (fabs(a - b) < 1e-8) return 0; //相同
    if (a > b) return 1; //a大于b
    if (a < b) return -1; //a小于b
}

void solve() {
    n = read(), m = read();
    for (int i = 0; i < n; i++) scanf("%lf%lf", &node[i].first, &node[i].second);
    memset(seg, 0, sizeof seg);
    for (int i = 0; i < n; i++) {
        seg[i][i] = 1 << i; //一条直线
        for (int j = 0; j < n; j++) {
            //两个点确定一条抛物线
            double x = node[i].first, y = node[i].second;
            double xx = node[j].first, yy = node[j].second;
            double a = (y / x - yy / xx) / (x - xx);
            double b = (y / x - a * x);
            if (cmp(a, 0.0) != -1) continue; //抛物线开口向上，舍去
            for (int k = 0; k < n; k++) {
                double u = node[k].first, v = node[k].second;
                if (cmp(a * u * u + b * u, v) == 0) 
                    seg[i][j] += 1 << k; //能够杀死这头猪
            }

        }
    }
    memset(dp, 0x3f, sizeof dp);
    dp[0] = 0;
    for (int st = 0; st < (1 << n) - 1; st++) {
        int pos = -1;
        for (int i = 0; i < n; i++)
            if (!(st >> i & 1))
                pos = i;
        for (int i = 0; i < n; i++) {
            int nxt = seg[pos][i] | st;
            dp[nxt] = min(dp[nxt], dp[st] + 1);
        }
    }
    printf("%lld\n", dp[(1 << n) - 1]);
}

区间DP模型

环形石子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
ll n;
ll a[MAXN];
ll mx[MAXN][MAXN], mn[MAXN][MAXN];
ll sum[MAXN];
void solve() {
    n = read();
    for (int i = 1; i < n; i++) {
        a[i] = read();
        a[i + n] = a[i];
    }
    a[n] = read();
    ll N = 2 * n - 1;
    for (int i = 1; i <= N; i++) sum[i] = sum[i - 1] + a[i];
    memset(mn, 0x3f, sizeof mn);
    memset(mx, ~0x3f, sizeof mx);
    for (int len = 1; len <= n; len++) {
        for (int l = 1, r; r = l + len - 1, r <= N; l++) {
            if (l == r) {
                mn[l][r] = 0;
                mx[l][r] = 0;
            }
            else {
                for (int k = l; k < r; k++) {
                    //[l,k] [k+1,r]
                    mx[l][r] = max(mx[l][k] + mx[k + 1][r] + sum[r] - sum[l - 1], mx[l][r]);
                    mn[l][r] = min(mn[l][k] + mn[k + 1][r] + sum[r] - sum[l - 1], mn[l][r]);
                }
            }
        }
    }
    ll MN = INF, MX = -INF;
    for (int i = 1; i <= n; i++) {
        MN = min(MN, mn[i][i + n - 1]);
        MX = max(MX, mx[i][i + n - 1]);
    }
    printf("%lld\n%lld\n", MN, MX);
}

**题目：**给定一个含有 nn 个节点的二叉树的中序遍历序列中每个节点的权值。定义一棵子树的分数为 左子树的分数 ×\times 右子树的分数 ++ 根节点的权值。规定空树的分数为 11 。求一种方案，使得分数最大。

区间内枚举根节点的位置即可

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
ll n;
ll a[MAXN];
ll dp[MAXN][MAXN];
int rt[MAXN][MAXN];

void dfs(int now, int l, int r) {
    if (l > r) return;
    printf("%d ", now);
    dfs(rt[l][now - 1], l, now - 1);
    dfs(rt[now + 1][r], now + 1, r);
}

void solve() {
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    memset(dp, ~0x3f, sizeof dp);
    for (int len = 1; len <= n; len++) {
        for (int l = 1, r; r = l + len - 1, r <= n; l++) {
            if (len == 1) {
                dp[l][r] = a[l];
                rt[l][r] = l;
            }
            else {
                for (int k = l; k <= r; k++) { //枚举一段区间内的根节点
                    ll lscore = k == l? 1ll: dp[l][k - 1];
                    ll rscore = k == r? 1ll: dp[k + 1][r];
                    ll score = lscore * rscore + a[k];
                    if (score > dp[l][r]) {
                        dp[l][r] = score;
                        rt[l][r] = k;
                    }
                }   
            }
        }
    }
    printf("%lld\n", dp[1][n]);
    dfs(rt[1][n], 1, n);
}

题目： 给出一个 1×n1 \times n 的空间玩 20482048 。每次可以合并相邻两个数，合并后的数值加一。求最后序列中的最大值。

考察了完全合并，即区间内所有数必须合并才能进行状态转移。

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
ll dp[MAXN][MAXN];
ll n;
ll a[MAXN];
void solve() {
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    ll ans = 0;
    for (int len = 1; len <= n; len++) {
        for (int l = 1, r; r = l + len - 1, r <= n; l++) {
            if (l == r)
                dp[l][r] = a[l], ans = max(ans, a[l]);
            else {
                for (int k = l; k < r; k++) {
                    int lmx = dp[l][k];
                    int rmx = dp[k + 1][r];
                    if (lmx == 0 || rmx == 0 || lmx != rmx) continue;
                    
                    dp[l][r] = lmx + 1;
                    ans = max(ans, dp[l][r]);
                }
            }
        }
    }
    printf("%lld\n", ans);
}

题目： 给出以序列，每个可以删除一段连续的回文串，问最少几次操作能全删光。

  • 长度为 11 ，dp[l][r]=1dp[l][r]=1

  • 长度为 22

    • 相同，dp[l][r]=1dp[l][r] = 1
    • 不相同，dp[l][r]=2dp[l][r]=2

  • 长度大于 22

    • 首尾不相同 dp[l][r]=min(dp[l][k],dp[k+1][r])dp[l][r] = min(dp[l][k],dp[k+1][r])
    • 首尾相同，取最小值时加个 dp[i+1][j−1]dp[i+1][j-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
ll n;
ll a[MAXN];
ll dp[MAXN][MAXN];
void solve() {
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    memset(dp, 0x3f, sizeof dp);
    for (int len = 1; len <= n; len++) {
        for (int l = 1, r; r = l + len - 1, r <= n; l++) {
            if (len == 1)
                dp[l][r] = 1;
            else if (len == 2) {
                if (a[l] == a[r])
                    dp[l][r] = 1;
                else
                    dp[l][r] = 2;
            }
            else {
                for (int k = l; k < r; k++)
                    dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);
                if (a[l] == a[r])
                    dp[l][r] = min(dp[l][r], dp[l + 1][r - 1]);
            }
        }
    }
    printf("%lld\n", dp[1][n]);   
}

树形DP模型

树上背包参考前面的有依赖的背包问题部分

核心就是先一路递归下去直到叶子节点，然后用已知的子节点状态更新父节点状态。当需要再用父节点状态来更新子节点时，用换根DP

求树的直径

一共有三种路径：

  • 以子树中的某个节点作为起点，以它作为终点
  • 以子树中的某个节点作为起点，以子树中的某个节点作为终点
  • 以子树中的某个节点作为起点，以非其子树中的某个节点作为终点

第一种情况可以找出最长路径，第二种情况可以顺便找最长路径的时候找出次长路径，第三种情况可以归类于某个祖先节点的最长路径和次长路径。

所以树形DP维护两个东西，以节点 ii 为根的子树中，以某个节点到 ii 的最长路径和次长路径。

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
ll ans1 = -INF, ans2 = -INF, ans;
ll n;

ll dfs(int now, int pre) {
    ll mx = 0;
    for (int i = head[now]; i; i = edge[i].next) {
        int to = edge[i].to;
        int val = edge[i].val;
        if (to == pre) continue;
        ll tmp = val + dfs(to, now);
        mx = max(mx, tmp);
        
        if (tmp > ans1) {
            ans2 = ans1;
            ans1 = tmp;
        }
        else if (tmp <= ans1 && tmp > ans2) {
            ans2 = tmp;
        }
        ans = max(ans, ans1 + ans2);
    }
    return mx;
}

void solve() {
    n = read();
    for (int i = 1; i < n ; i++) {
        ll u = read(), v = read(), w = read();
        add_edge(u, v, w);
        add_edge(v, u ,w);
    }
    dfs(1, -1);
    printf("%lld\n", ans);
}

题目： 给出一个带边权的树形图，要求根节点到所有叶子节点的距离都相等。每次可以用 11 的代价使任意一条边的边权加 11 。问最小花费。

有一个关键点，假设某个节点向儿子的连边需要增加的长度为 3,5,83,5,8 ，实际上可以把 33 塞到向父亲节点的连边中，这样花费就变少了。这就是核心的贪心思路。

那么第一次 dfsdfs 把所有节点的深度都求出来。第二次找到所有子节点连边中最小需要增加的长度，然后把这个长度转移到父亲节点的连边并减去贡献。特判叶子节点。定义 dpdp 数组为向父亲节点连边的长度。

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
ll depth[MAXN], mxdep;
ll dp[MAXN]; //i节点连向父亲的边的长度
ll ans = 0;
void dfs_pre(int now, int pre) {
    for (int i = head[now]; i; i = edge[i].next) {
        int to = edge[i].to;
        ll val = edge[i].val;
        if (to == pre) continue;
        depth[to] = depth[now] + val;
        mxdep = max(mxdep, depth[to]);
        dfs_pre(to, now);
    }
}

void dfs(int now, int pre) {
    int cnt = 0; ll mn = INF;
    for (int i = head[now]; i; i = edge[i].next) {
        int to = edge[i].to;
        ll val = edge[i].val;
        if (to == pre) continue;
        dfs(to, now);
        cnt++;
        mn = min(mn, dp[to]);
    }
    if (!cnt) {
        dp[now] = mxdep - depth[now];
        ans += dp[now];
        return;
    }
    if (now != rt) {
        dp[now] = mn;
        ans -= (cnt - 1) * mn;
    }
}

void solve() {
    n = read(), rt = read();
    for (int i = 1; i < n; i++) {
        int u, v; ll val;
        u = read(), v = read(), val = read();
        add(u, v, val);
        add(v, u, val);
    }
    dfs_pre(rt, -1);
    dfs(rt, -1);
    printf("%lld\n", ans);
}

换根DP

有两种最长路径：

  • 从当前节点往下，知道子树中某个节点的最长路径
  • 从当前节点往上，再从其父节点出发且不回到该节点的最长路径

换根DP分两个步骤。一次dfs统计出当前子树内的节点对当前节点的贡献。再一次dfs遍历，统计出当前节点的父节点对当前节点的贡献。然后合并统计答案。

那么第一遍dfs预处理出儿子的最大贡献距离和次大贡献距离以及最大贡献儿子和次大贡献儿子的编号。因为如果当前节点是其父节点子树中最大路径上的点，则父节点子树的最大贡献不能算作对该节点的贡献，要取父节点的次大贡献。

dfsdfs 注意顺序。第一次用子节点更新父亲（自下而上），所以先 dfsdfs ；第二次用父亲更新儿子（自上而下），所以求完后再 dfsdfs 。

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
int n;
int down1[MAXN], down2[MAXN], up[MAXN];
int son1[MAXN], son2[MAXN];

void dfs_down(int now, int pre) {
    for (int i = head[now]; i; i = edge[i].next) {
        int to = edge[i].to;
        int val = edge[i].val;
        if (to == pre) continue;
        dfs_down(to, now);
        if (down1[to] + val > down1[now]) {
            down2[now] = down1[now], son2[now] = son1[now];
            down1[now] = down1[to] + val, son1[now] = to;
        }
        else if (down1[to] + val > down2[now]) {
            down2[now] = down1[to] + val, son2[now] = to;
        }
    }
}

void dfs_up(int now, int pre) {
    for (int i = head[now]; i; i = edge[i].next) {
        int to = edge[i].to;
        int val = edge[i].val;
        if (to == pre) continue;
        if (son1[now] == to) {
            up[to] = val + max(up[now], down2[now]);
        }
        else {
            up[to] = val + max(up[now], down1[now]);
        }
        dfs_up(to, now); //最后再往下走
    }
}

void solve() {
    n = read();
    for (int i = 1; i < n; i++) {
        int u = read(), v = read(), w = read();
        add(u, v, w);
        add(v, u, w);
    }
    dfs_down(1, -1);
    dfs_up(1, -1);
    int ans = INF;
    for (int i = 1; i <= n; i++)
        ans = min(ans, max(down1[i], up[i]));
    printf("%d\n", ans);
}

题目： 有一个带点权（奶牛数量）和边权（路径长度）的树。现要找一个点作为开会地点，使得奶牛走的路程最小。

可以随便选择一个点作为根节点往下 dfsdfs 算出所有子节点到达这个选定根节点需要走的路程，然后进行换根 DPDP 。定义 dp[i]dp[i] 表示 ii 这个节点作为根节点时奶牛走过的路程和。易得出这个方程由两个地方转移过来，儿子的子树和父亲上面的部分。

假设有一条边，此时已经算出了 dp[now]dp[now] ，若将 toto 作为根节点，画图后可以发现包含 toto 在内的子树深度全部减去当前边权的大小，其他节点的深度都增加了当前边权的大小 。减少的大小为 siz[now]×valsiz[now]\times val ，增加的大小为 (n−siz[now])×val(n - siz[now])\times val 。因此可以用父节点来更新子节点的状态，典型的换根 DPDP 。

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
ll a[MAXN];
ll siz[MAXN], dp[MAXN], depth[MAXN];
ll n, N;

void dfs_down(int now, int pre) {
    siz[now] = a[now];
    dp[now] = depth[now] * a[now];
    for (int i = head[now]; i; i = edge[i].next) {
        int to = edge[i].to;
        ll val = edge[i].val;
        if (to == pre) continue;
        depth[to] = depth[now] + val;
        dfs_down(to, now);
        siz[now] += siz[to];
        dp[now] += dp[to];
    }
}

void dfs_up(int now, int pre) {
    for (int i = head[now]; i; i = edge[i].next) {
        int to = edge[i].to;
        ll val = edge[i].val;
        if (to == pre) continue;
        dp[to] = dp[now] - siz[to] * val + (N - siz[to]) * val;
        dfs_up(to, now);
    }
}

void solve() {
    n = read();
    for (int i = 1; i <= n; i++) {
        a[i] = read();
        N += a[i];
    }
    for (int i = 1; i < n; i++) {
        int u = read(), v = read();
        ll w = read();
        add(u, v, w);
        add(v, u, w);
    }
    dfs_down(1, -1);
    dfs_up(1, -1);
    ll ans = INF;
    for (int i = 1; i <= n; i++) {
        if (dp[i] < ans) {
            ans = dp[i];
        }
    }
    printf("%lld\n", ans);
}

题目： 给出一颗 nn 个点的树，点带权，对于每个节点求出距离它不超过 kk 的所有节点权值和 mim_i

k≤20k \leq 20

设 down[i][j]down[i][j] 表示从 ii 点向下 jj 的范围内由多少牛，dp[i][j]dp[i][j] 表示 ii 点的 jj 范围内有多少牛。

down[i][j]=a[i]+∑down[son][j−1]down[i][j] = a[i] + \sum{down[son][j - 1]} 。很好算，第一遍 dfsdfs 求出来

然后画个图，发现 dp[i][j]=dp[fa][j−1]−down[v][j−2]+down[v][j]dp[i][j] = dp[fa][j - 1] - down[v][j - 2] + down[v][j] 。又是要用父节点更新子节点，用换根 DPDP 。

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
ll n, k;
ll a[MAXN];
ll dp[MAXN][25];
ll down[MAXN][25];

void dfs_down(int now, int pre) {
    for (int i = 0; i <= k; i++) down[now][i] = a[now];
    for (int i = head[now]; i; i = edge[i].next) {
        int to = edge[i].to;
        if (to == pre) continue;
        dfs_down(to, now);
        for (int j = 1; j <= k; j++)
            down[now][j] += down[to][j - 1];
    }
}

void dfs_up(int now, int pre) {
    for (int i = head[now]; i; i = edge[i].next) {
        int to = edge[i].to;
        if (to == pre) continue;
        dp[to][1] += down[now][0];
        for (int j = 2; j <= k; j++)
            dp[to][j] += dp[now][j - 1] - down[to][j - 2]; 
        //此时now以完成更新，用父亲来更新儿子 
        dfs_up(to, now);
    }
}

void solve() {
    n = read(), k = read();
    for (int i = 1; i < n; i++) {
        int u = read(), v = read();
        add(u, v);
        add(v, u);
    }
    for (int i = 1; i <= n; i++) a[i] = read();
    dfs_down(1, -1);
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= k; j++)
            dp[i][j] = down[i][j];
    dfs_up(1, -1);
    for (int i = 1; i <= n; i++)
        printf("%lld\n", dp[i][k]);
}

树上状态机

题目： 没有上司的舞会。状态1当前节点参加：儿子节点一定不参加；状态2当前节点不参加：儿子节点可参加可不参加

题目： 给定一棵包含 nn 个节点的树。需要在节点上放置一些哨兵，哨兵的视野范围是一条边，使得所有边都能被哨兵观察到。

这个状态机定义起来很简单。若当前节点放置哨兵，子节点可放可不放；若当前节点未放置哨兵，子节点必须放。定义dp[i][1/0]dp[i][1/0] ：以节点 ii 为根节点的子树，在 ii 上放置哨兵(1)(1) 和不放哨兵(0)(0) 的方案数量。

dp[i][0]=∑dp[son][1]，dp[i][1]=∑min(dp[son][1],dp[son][0])dp[i][0] = \sum{dp[son][1]}，dp[i][1] = \sum{min(dp[son][1],dp[son][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
int dp[2][MAXN];
int n;

void init() {
    tot = 0;
    for (int i = 1; i <= n; i++) {
        head[i] = 0;
    }
    memset(dp, 0x3f, sizeof dp);
}

void dfs(int now, int pre) {
    dp[0][now] = 0, dp[1][now] = 1;
    for (int i = head[now]; i; i = edge[i].next) {
        int to = edge[i].to;
        if (to == pre) continue;
        dfs(to, now);
        dp[0][now] += dp[1][to];
        dp[1][now] += min(dp[0][to], dp[1][to]);
    }
}

void solve() {
    for (int i = 1; i <= n; i++) {
        int u, k;
        scanf("%d:(%d)", &u, &k);
        u++;
        while (k--) {
            int v = read();
            v++;
            add(u, v);
            add(v, u);
        }
    }
    dfs(1, -1);
    printf("%d\n", min(dp[1][1], dp[0][1]));
}

题目： 现在改成观察所有的点，且放置卫兵有代价，使得代价最小。

这样有三种状态：00 表示被父节点观察，11 表示被自己观察，22 表示被某个子节点观察

被父节点观察时，子节点要么被自己观察要么被其子节点观察

被自己观察时，子节点可以被父节点观察，可以被自己观察，也可以被其子节点观察

被子节点观察时，其中一个子节点必须被自己观察，其他子节点状态同 00 。

其他都一样，就是多出来的这个状态最后找出代价最小的子节点，在 dp[now][0]dp[now][0] 减去这个子节点的贡献，再加上 dp[to][1]dp[to][1] ，就是 22 状态的花费代价。

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
int n;
ll a[MAXN];
ll dp[3][MAXN];
//0表示被父亲观察，1表示被自己观察，2表示被儿子观察
//0的话儿子要么被自己观察，要么被自己的儿子观察
//1的话儿子被自己，父亲，儿子观察
//2的话儿子被自己观察的状态中找一种最小的方案，其余的儿子和0同理

void dfs(int now, int pre) {
    dp[0][now] = 0, dp[1][now] = a[now], dp[2][now] = INF;
    for (int i = head[now]; i; i = edge[i].next) {
        int to = edge[i].to;
        if (to == pre) continue;
        dfs(to, now);
        dp[0][now] += min(dp[1][to], dp[2][to]);
        dp[1][now] += min({dp[0][to], dp[1][to], dp[2][to]});
    }
    for (int i = head[now]; i; i = edge[i].next) {
        int to = edge[i].to;
        if (to == pre) continue;
        dp[2][now] = min(dp[2][now], dp[0][now] - min(dp[1][to], dp[2][to]) + dp[1][to]);
    }
}

void solve() {
    n = read();
    for (int i = 1; i <= n; i++) {
        int k, u;
        u = read(), a[u] = read(), k = read();
        while (k--) {
            int v = read();
            add(u, v);
            add(v, u);
        }
    }
    dfs(1, -1);
    printf("%lld\n", min(dp[1][1], dp[2][1]));
}

数位DP模型

数位：把一个数字按照个、十、百、千等等一位一位地拆开，关注它每一位上的数字。如果拆的是十进制数，那么每一位数字都是 0→90 \rightarrow 9 ，其他进制可类比十进制。

数位DP：用来解决一类特定问题，一般具有以下特征

  • 要求统计满足一定条件的数的数量（集合属性为方案数）
  • 条件经过转化后可以使用或者类比数位的思想去理解和判断
  • 输入会提供一个区间范围作为统计的限制
  • 上界很大，大到暴力会超时

题目要求一段区间内符合条件的数的个数，可以用前缀和思想转化为求两个前缀区间的问题。

sum[l,r]=sum[1,r]−sum[1,l−1]sum[l,r]=sum[1,r]-sum[1,l-1]

统计答案可以选择记忆化搜索。为了不重不漏地统计所有不超过上限的答案，要从高到低枚举每一位，在考虑每一位都可以填哪些数字，最后利用前缀和思想统计答案。

记忆化搜索中要引入的参数通常由：

  • 当前枚举到的数位 pospos
  • 前几位搜索过的情况 stst （视题目而定，如前一位是什么，前几位的总和，某个数出现了几次）
  • 前几位的数字是否等于上界的前几位数字 limit(0/1)limit(0/1)
  • 是否有前导零 lead(0/1)lead(0/1)

关于递归时的树型结构会在第一道例题中解释

使用记忆化搜索是为了优化当前搜索分支（废话），那么什么时候可以呢？就是在当前数位能够枚举集合内所有元素的时候（前面搜索的数没有紧密贴着上界），即!limit!limit

抄来的伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int dfs(int pos, int pre, int lead, int limit) {
    if (!pos) {
        边界条件
    }
    if (!limit && !lead && dp[pos][pre] != -1) return dp[pos][pre];
    int res = 0, up = limit ? a[pos] : 无限制位;
    for (int i = 0; i <= up; i ++) {
        if (不合法条件) continue;
        res += dfs(pos - 1, 未定参数, lead && !i, limit && i == up);
    }
    return limit ? res : (lead ? res : dp[pos][sum] = res);
}
int cal(int x) {
    memset(dp, -1, sizeof dp);
    len = 0;
    while (x) a[++ len] = x % 进制, x /= 进制;
    return dfs(len, 未定参数, 1, 1);
}
int main() {
    cin >> l >> r;
    cout << cal(r) - cal(l - 1) << endl;
    return 0;
}

预处理基本参数：

  • len：len： 数位长度，一般根据这个来确定数组范围
  • ai：a_i： 每个数位的具体数字（上限）

dfsdfs 函数：

  • if (!limit && !lead && ~dp[pos][pre]) return dp[pos][pre]; 只有无数位大小限制，无前导零的情况才算，不然都是未搜索完的情况
  • return limit ? res : dp[pos][pre] = res; 如果最后还有限制，返回 resres , 否则返回 dp[pos][res]dp[pos][res] 并记忆化

记忆化搜索基本参数：

  • pospos （必填），表示数字的位数（当前搜索的深度）。一般是选择 a[1]a[1] 到 a[n]a[n] 的顺序，边界条件为 !pos!pos
  • limitlimit （必填），可以填数的限制。无限制的话从 0→90 \rightarrow 9 随便填，否则只能填到 a[i]a[i]
  • prepre （选填），表示上一个数是多少
  • leadlead （选填），前导零是否存在，1表示存在
  • sumsum （选填），搜索到当前数字所有数字之和
  • cntcnt （选填），某个数字出现的次数

题目： 求给定区间 [L,R][L,R] 满足：这个数恰好等于 KK 个互不相等的 BB 的整数次幂之和。

本题较为特殊，对于该 BB 进制的数来说，每位要么填 00 要么填 11（互不相同） ，且填 11 的个数恰好等于 KK 。stst 记录的就是前几位填过的 11的个数，本题不用考虑前导零。

定义状态为 解除限制后，前 ii 位 11 出现过 jj 次时的方案数。此题中方案数对应数的个数

image-20220717193832953

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
int l, r, k, b;
int a[MAXN], al;
int dp[MAXN][MAXN];

int dfs(int pos, int cnt, int limit) {
    //枚举完所有数，看1出现的次数是否等于k
    if (!pos) return cnt == k;
    //当前限制以解除，返回记忆化结果
    if (!limit && ~dp[pos][cnt]) return dp[pos][cnt];
    //这个状态还没出现过，往下搜
    int ans = 0;
    int up = limit ? a[pos] : 1;
    for (int i = 0; i <= up; i++) {
        if (cnt + i > k) continue;
        if (i > 1) continue;
        ans += dfs(pos - 1, cnt + i, limit && i == up);
    }
    return limit ? ans : dp[pos][cnt] = ans;
}

int calc(int x) {
    al = 0;
    memset(dp, -1, sizeof dp);
    while (x) {
        a[++al] = x % b;
        x /= b;
    }
    return dfs(al, 0, 1);
}

void solve() {
    l = read(), r = read(), k = read(), b = read();
    printf("%d\n", calc(r) - calc(l - 1));
}

题目： 统计 [L,R][L,R] 范围内 0123456789 出现的次数

需要判断前导零。并且注意一下和前导零相关的边界问题。若最后的数字是0，返回1；若还未解除前导零的限制且当前找的数是0，那么 00 出现的次数应该不变始终为 00 。

定义 dp[i][j]dp[i][j] 为解除限制后前 ii 位 kk 这个数字（通过外层枚举来求得 kk） 出现了 jj 次的方案数。本题的方案数对应 kk 这个数字出现的次数。

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
int l, r;
int a[MAXN], al;
int dp[MAXN][MAXN]; //前i位num出现过j次的方案数

int dfs(int pos, int cnt, int num, int lead, int limit) {
    if (!pos) {
        if (!num && lead)
            return 1; //所有位上都是0
        else
            return cnt; //返回num出现过的次数
    }
    if (!limit && !lead && ~dp[pos][cnt]) return dp[pos][cnt];
    int ans = 0;
    int up = limit ? a[pos] : 9;
    for (int i = 0; i <= up; i++) {
        int nxt;
        if (i == num) {
            //如果i是要找的那个数
            if (!num) //要找的数是0，那么前导零的限制必须已解除
                nxt = cnt + !lead;
            else
                nxt = cnt + 1;
        }
        else
            nxt = cnt;
        ans += dfs(pos - 1, nxt, num, lead && !i, limit && i == up);
    }
    return limit ? ans : (lead ? ans : dp[pos][cnt] = ans);
}

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

void solve() {
    for (int i = 0; i <= 9; i++) {
        printf("%d ", calc(r, i) - calc(l - 1, i));
    }
    puts("");
}

int main() {
    while (scanf("%d%d", &l, &r), l || r) {
        if (l > r) swap(l, r);
        solve();
    }
    return 0;
}

题目： 找出给定 [L,R][L,R] 区间内相邻数位之差大于 22 的数字个数。

要考虑前导零。定义状态 dp[i][j]dp[i][j] 为 解除限制后 第 ii 位数字为 jj 时的方案数，本题方案数对应合法数字的个数。

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
int l, r;
int a[MAXN], al;
int dp[MAXN][MAXN]; //第i位数为j时的方案数

int dfs(int pos, int pre, int lead, int limit) {
    if (!pos) {
        return 1;
    }
    if (!limit && !lead && ~dp[pos][pre]) return dp[pos][pre];
    int ans = 0;
    int up = limit ? a[pos] : 9;
    for (int i = 0; i <= up; i++) {
        if (abs(i - pre) < 2) continue;
        if (lead && !i)
            ans += dfs(pos - 1, -2, 1, limit && i == up);
        else
            ans += dfs(pos - 1, i, 0, limit && i == up);
    }
    return limit ? ans : (lead ? ans : dp[pos][pre] = ans);
}

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

void solve() {
    l = read(), r = read();
    printf("%d\n", calc(r) - calc(l - 1));
}

题目： 找出 [L,R][L,R] 范围内从左到右数位非下降的数字的个数

不用考虑前导零，记录前驱就行。定义状态 dp[i][j]dp[i][j] 为 解除限制后 第 ii 位数字为 jj 时的方案数，本题方案数对应数字的个数

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
int l, r;
int a[MAXN], al;
int dp[MAXN][MAXN];

int dfs(int pos, int pre, int limit) {
    if (!pos) {
        return 1;
    }
    if (!limit && ~dp[pos][pre]) return dp[pos][pre];
    int ans = 0;
    int up = limit ? a[pos] : 9;
    for (int i = 0; i <= up; i++) {
        if (i < pre) continue;
        ans += dfs(pos - 1, i, limit && i == up);
    }
    return limit ? ans : dp[pos][pre] = ans;
}

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

void solve() {
    printf("%d\n", calc(r) - calc(l - 1));
}

int main() {
    while (scanf("%d%d", &l, &r) != EOF) {
        solve();
    }
    return 0;
}

题目： 给定 [L,R][L,R] 区间内有多少数字的数位和是 NN 的倍数，（N由题目给出）。

不用考虑前导零，不用考虑前驱，记录一个 sumsum 表示数位和即可，边界条件是 !pos && sum % mod == 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
int l, r, mod;
int a[MAXN], al;
int dp[MAXN][105];

int dfs(int pos, int sum, int limit) {
    if (!pos) {
        if (sum % mod == 0) return 1;
        return 0;
    }
    if (!limit && ~dp[pos][sum]) return dp[pos][sum];
    int ans = 0;
    int up = limit ? a[pos] : 9;
    for (int i = 0; i <= up; i++) {
        ans += dfs(pos - 1, sum + i, limit && i == up);
    }
    return limit ? ans : dp[pos][sum] = ans;
}

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

void solve() {
    printf("%d\n", calc(r) - calc(l - 1));
}

int main() {
    while (scanf("%d%d%d", &l, &r, &mod) != EOF) {
        solve();
    }
    return 0;
}

题意： 求 11 到 nn 中每个数的二进制下的 11 的个数的累乘。

不用考虑前导零，因为只关心 11的个数不关心排列方式。二进制拆分后得到长度 lenlen 作为搜索深度。定义 dp[i][j]dp[i][j] 为前 ii 位出现了 jj 个 11 时的方案数，本题方案数定义为 11的个数的累乘。由于求累乘，所有 ansans 一开始要赋为 11 ，另外边界的时候也要特判一下

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
ll dp[MAXN][MAXN];
ll r;
int a[MAXN], al;

ll dfs(int pos, int cnt, int limit) {
    if (!pos) {
        return max(1ll, (ll)cnt);
    }
    if (!limit && ~dp[pos][cnt]) return dp[pos][cnt];
    ll ans = 1;
    int up = limit ? a[pos] : 1;
    for (int i = 0; i <= up; i++) {
        int t = cnt;
        if (i) t++;
        ans = ans * dfs(pos - 1, t, limit && i == up) % mod;
    }
    return limit ? ans : dp[pos][cnt] = ans;
}

ll calc(ll x) {
    memset(dp, -1, sizeof dp);
    al = 0;
    while (x) {
        a[++al] = x % 2;
        x /= 2;
    }
    return dfs(al, 0, 1);
}

int main() {
    scanf("%lld", &r);
    printf("%lld\n", calc(r));
    return 0;
}

单调队列优化DP模型

一般分为两种情况：

  • 题目中给定一个区间范围 kk ，通过这个 kk 去思考
  • 题目中为给出明确的，具体的，不可更改的范围，但是需要考虑到第 ii 位之前 [i−k,i−1][i-k,i-1] 区间的前缀和问题

题目： 求 1≤len≤k1 \leq len \leq k 的最大连续子序列和。

维护一个前缀和的单调队列。因为是前缀和，所以要预先插入一个 00 来处理边界问题。

求最大前缀和，每次用当前的 sum[i]sum[i] 减去 sum[q[hh]]sum[q[hh]] 就是值，因为要最大所以队头要最小。

另外，长度大于等于1，也就是队头不能等于当前的 ii ，所以在先求最值再把当前的 ii 插入队尾。否则可能出现队头队尾相同的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int n, k;
ll sum[MAXN], a[MAXN];
int q[MAXN];
int hh = 1, tt = 0;
void solve() {
    n = read(), k = read();
    for (int i = 1; i <= n; i++) {
        a[i] = read();
        sum[i] = sum[i - 1] + a[i]; 
    }
    ll ans = -INF;
    //枚举以i作为终点的，长度不超过k的最大子序和
    q[++tt] = 0;
    for (int i = 1; i <= n; i++) {
        while (hh <= tt && i - q[hh] > k) hh++;
        ans = max(ans, sum[i] - sum[q[hh]]);
        while (hh <= tt && sum[q[tt]] >= sum[i]) tt--;
        q[++tt] = i;
        
    }
    printf("%lld\n", ans);
}

单调队列实在是不会写，写一道意思意思。

概率期望DP模型

一般思路：由于起点往往只有 11 个，终点有多个，因此需要倒着考虑。就像树形DP用子节点更新父节点那种思想，用记忆化搜索做。可以设 dp[i]dp[i] 表示从状态 ii 到状态 nn 的期望，那么 dp[1]dp[1] 即为总期望。

性质： E(ax+by)=aE(x)+bE(y)E(ax+by) = aE(x) + bE(y)

绿豆蛙的归宿： 给出一个有边权的 DAGDAG 图。如果有 kk 条离开某个点的道路，绿豆蛙可以选择任意一条道路离开该点，并且概率为 1k\frac{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
ll n, m;
vector<pii> g[MAXN];
double dp[MAXN]; //以i作为起点，到达各个终点的路径期望之和

double dfs(int now) {
    if (dp[now] >= 0) {
        //已经搜索过了
        return dp[now];
    }
    int len = g[now].size();
    dp[now] = 0.0;
    for (int i = 0; i < len; i++) {
        int to = g[now][i].first;
        double val = g[now][i].second + 0.0;
        dp[now] += (val + dfs(to)) / (len + 0.0);
    }
    return dp[now];
}

void solve() {
    n = read(), m = read();
    memset(dp, ~0x3f, sizeof dp);
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        u = read(), v = read(), w = read();
        g[u].pb(v, w);
    }
    dfs(1);
    printf("%.2lf\n", dp[1]);
}