$ Dynamic \ Programming $

$$
Tecy
$$

线性 $dp$ 引入

Frog 1

问题陈述

有$N$块石头，编号为$1, 2, \ldots, N$。每块$i$（$1 \leq i \leq N$），石头$i$的高度为$h_i$。

有一只青蛙，它最初在$1$号石头上。它会重复下面的动作若干次以到达石块$N$：

  • 如果青蛙目前在石块$i$上，则跳到石块$i + 1$或石块$i + 2$上。这里需要付出$|h_i - h_j|$的代价，其中$j$是要降落的石块。

求青蛙到达石块$N$之前可能产生的最小总成本。

$f_{i}$ 表示到达 $i$ 所需花费

$ f_{i} = min(f_{i - 1} + |h_{i} - h_{i - 1}|, f_{i - 2} + |h_{i} - h_{i - 2}|)$

复杂度 $O(N)$

main code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int n;
cin >> n;
vector<int> val(n);
for(auto& x : val){
	cin >> x;
}

vector<int> f(n);
f[1] = abs(val[1] - val[0]);
for(int i = 2; i < n; i++){
	f[i] = min(f[i - 1] + abs(val[i] - val[i - 1]), 
               f[i - 2] + abs(val[i] - val[i - 2]));
}

cout << f.back();

Frog 2

问题陈述

有$N$块石头，编号为$1, 2, \ldots, N$。每块$i$（$1 \leq i \leq N$），石头$i$的高度为$h_i$。

有一只青蛙，它最初在石块 $1$ 上。它会重复下面的动作若干次以到达石块$N$：

  • 如果青蛙目前在石块$i$上，请跳到以下其中一个位置：石块$i + 1, i + 2, \ldots, i + K$。这里会产生$|h_i - h_j|$的代价，其中$j$是要降落的石头。

求青蛙到达石块$N$之前可能产生的最小总成本。

$f_{i}$ 表示到达 $i$ 所需花费

$ f_{i} = min(f_{i - j} + |h_{i} - h_{i - j}|) \quad if \quad j \le k $

复杂度 $O(K \times N)$

main code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const int inf = 1e9;
int n, k;
cin >> n >> k;
vector<int> val(n);
for(auto& x : val){
    cin >> x;
}

vector<int> f(n, inf);
f[0] = 0;
for(int i = 1; i < n; i++){
    for(int j = 1; j <= k; j++){
        if(i - j >= 0){
            f[i] = min(f[i], f[i - j] + abs(val[i] - val[i - j]));
        }
    }
}

cout << f.back();

经典 $dp$

LCS

问题陈述

给你字符串 $s$ 和 $t$。请找出一个最长的字符串，它同时是 $s$ 和 $t$ 的子串。

$f_{i, j}$ 表示考虑 $s$ 前 $i$ 个， $t$ 前 $j$ 个最长子串
$$
f_{i, j} =
\begin{cases}
f_{i - 1, j - 1} + 1 \quad \quad \quad \ \ \ if \quad s[i] = t[j] \
max(f_{i, j - 1}, f_{i - 1, j}) \quad if \quad s[i] \neq t[j]
\end{cases}
$$
求出长度后，反向可推出最长公共子串（不唯一）
$$
if \quad s[i] == t[j] \rightarrow s[i]
$$

复杂度 $O(|s| \times |t|)$

main code

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
string s, t;
cin >> s >> t;
s = " " + s;
t = " " + t;    
int n = s.size();
int m = t.size();
vector<vector<int>> f(n, vector<int>(m));
for(int i = 1; i < n; i++){
    for(int j = 1; j < m; j++){
        if(s[i] == t[j]){
            f[i][j] = f[i - 1][j - 1] + 1;
        }else{
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
        }
    }
}
int sp = n - 1;
int tp = m - 1;
string ans = "";
while(sp >= 1 && tp >= 1){
    if(s[sp] == t[tp]){ //
        ans += s[sp];
        sp--;
        tp--;
    }else{
        if(f[sp][tp] == f[sp - 1][tp]){
            sp--;
        }else{
            tp--;
        }
    }
}
reverse(ans.begin(), ans.end());
cout << ans;

不能用 $f_{i, j} = f_{i - 1, j - 1} + 1 \quad \rightarrow \quad s[i]$

因为当 $f_{i, j} = f_{i - 1, j}$ 且 $f_{i - 1, j} = f_{i - 2, j} + 1$ 且 $f_{i, j} = f_{i - 1, j - 1} + 1$ 时会错

LIS

问题陈述。

方法一：

数列 $ a_{i} $ ，求最长不下降子序列。
$$
f_{i} = max(f_{j} + 1) \quad if \quad a_{i} \ge a_{j} \quad and \quad i \ge j
$$
复杂度 $O(N^{2})$

方法一 main code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const long long inf = 1e18;
int n;
cin >> n;
vector<long long> val(n + 1, -inf);
for(int i = 1; i <= n; i++){
    cin >> val[i];
}
vector<int> f(n + 1);
for(int i = 1; i <= n; i++){
    for(int j = 0; j < i; j++){
        if(val[i] >= val[j]){
            f[i] = max(f[i], f[j] + 1);
        }
    }
}
cout << *max_element(f.begin(), f.end());

方法二：

考虑进来一个元素 $a_{i}$ ：

  1. $d \ is \ empty$ 或元素大于等于 $d.back()$ ，直接将该元素插入到 $d$ 序列的末尾。
  2. 元素小于 $d.back()$ ，找到 第一个 大于等于它的元素，用 $a_{i}$ 替换它。

复杂度 $O(N log N)$

方法二 main code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int n;
cin >> n;
vector<long long> val(n);
for(auto& x : val){
    cin >> x;
}
vector<long long> d;
for(auto& x : val){
    if(d.empty() || d.back() <= x){
        d.push_back(x);
    }else{
        int p = lower_bound(d.begin(), d.end(), x) - d.begin();
        d[p] = x;
    }
}
cout << d.size();Q

拓展 LCIS

求两个串的最长公共上升子序列

结合以上就可解决本题。

$f_{i, j}$ 表示 $s[1 - i], t[1 - j]$ 以 $t[j]$ 结尾 $LCIS$ 的长度
$$
f_{i, j} = f_{i - 1, j} \quad if \quad s[i] \neq t[j]
$$

$$
f_{i, j} = max(f_{i - 1, k} + 1) \quad if \quad s[i] = t[j] \quad and \quad s[i] > t[k] \quad and \quad j > k
$$
复杂度 $O(N^{3})$

main code

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;
cin >> n;
vector<int> s(n + 1, -1);
for(int i = 1; i <= n; i++){
    cin >> s[i];
} 
int m;
cin >> m;
vector<int> t(m + 1, -1);
for(int i = 1; i <= m; i++){
    cin >> t[i];
}
int ans = 0;
vector<vector<int>> f(n + 1, vector<int>(m + 1));
vector<vector<int>> p(n + 1, vector<int>(m + 1));
for(int i = 1; i <= n; i++){
    for(int j = 1; j <= m; j++){
        if(s[i] == t[j]){
            for(int k = 0; k < j; k++){
                if(s[i] > t[k]){
                    if(f[i - 1][k] + 1 > f[i][j]){// 记录转移路径
                        p[i][j] = k;
                    }
                    f[i][j] = max(f[i][j], f[i - 1][k] + 1);
                }
            }
        }else{
            p[i][j] = p[i - 1][j];             
            f[i][j] = f[i - 1][j];
        }
    }
}
int tp = m;
for(int i = 1; i <= m; i++){
    if(ans < f[n][i]){
        ans = f[n][i];
        tp = i;
    }
}
vector<int> res;
while(ans > 0){
    res.push_back(t[tp]);
    tp = p[n][tp]; 
    ans--;
}
reverse(res.begin(), res.end());
cout << res.size() << "\n";
for(auto& x : res){
    cout << x << " ";
}

优化

该题还可优化为 $O(N^{2})$

可以看到枚举 $k$ 时 $s[i] = t[j]$ 这个条件不用检查，只用检查 $s[i] \ge t[k]$，枚举时决策取最大即可

$prefix_max_{i, j}$ 表示 $f[1 - i][1 - j]$ 的最大值
$$
f_{i, j} = f_{i - 1, j} \quad if \quad s[i] \neq t[j]
$$

$$
f_{i, j} = prefix_max_{i - 1, j - 1} + 1 \quad if \quad s[i] = t[j]
$$

$$
prefix_max_{i - 1, j} = max(prefix_max_{i - 1, j - 1}, f_{i - 1, j}) \quad if \quad s[i] > t[j]
$$

main code

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
int n;
cin >> n;
vector<int> s(n + 1, -1);// #
for(int i = 1; i <= n; i++){
    cin >> s[i];
} 

int m;
cin >> m;
vector<int> t(m + 1, -1);// #
for(int i = 1; i <= m; i++){
    cin >> t[i];
}

int ans = 0;
vector<vector<int>> f(n + 1, vector<int>(m + 1));
vector<vector<int>> p(n + 1, vector<int>(m + 1));
for(int i = 1; i <= n; i++){
    int to = 0;
    int prefix_max = 0;
    for(int j = 1; j <= m; j++){
        if(s[i] == t[j]){
            if(prefix_max + 1 > f[i][j]){// 记录转移路径
                p[i][j] = to;
            }
            f[i][j] = max(f[i][j], prefix_max + 1);
        }else{
            p[i][j] = p[i - 1][j];
            f[i][j] = f[i - 1][j];
        }

        if(s[i] > t[j]){
            if(prefix_max < f[i - 1][j]){
                to = j;
            }
            prefix_max = max(prefix_max, f[i - 1][j]);
        }
    }
}

int tp = m;
for(int i = 1; i <= m; i++){
    if(ans < f[n][i]){
        ans = f[n][i];
        tp = i;
    }
}

vector<int> res;
while(ans > 0){
    res.push_back(t[tp]);
    tp = p[n][tp]; 
    ans--;
}
reverse(res.begin(), res.end());

cout << res.size() << "\n";
for(auto& x : res){
    cout << x << " ";
}

背包

0-1背包

题意概要：有 $n$ 个物品和一个容量为 $v$ 的背包，每个物品有重量 $cost_{i}$ 和价值 $value_{i}$ 两种属性，要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量。(每个物品最多选一次)

$f_{i, j}$ 表示考虑前 $i$ 个物品，当前容量为 $j$ 是最优解
$$
f_{i, j} = max(f_{i - 1, j - cost_{i}} + value_{i}) \quad if \quad j \ge cost_{i}
$$
$$
f_{i, j} = f_{i - 1, j} \quad if \quad j < cost_{i}
$$

为什么要先枚举 $i$ ，后枚举 $j$ ？

物品被选多次。

main code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int n, m;
cin >> n >> m;
vector<int> cost(n + 1), value(n + 1);
for(int i = 1; i <= n; i++){
    cin >> cost[i] >> value[i];
}

vector<vector<int>> f(n + 1, vector<int>(m + 1));
for(int i = 1; i <= n; i++){
    for(int j = 0; j <= m; j++){
        if(j >= cost[i]){
            f[i][j] = max(f[i - 1][j], f[i - 1][j - cost[i]] + value[i]);
        }else{
            f[i][j] = f[i - 1][j];
        }
    }
}

cout << f[n][m];

一维优化空间 $f_{j} = max(f_{j - cost_{i}})$

复杂度 $O(n \times v)$

要倒序枚举 $j$ !!!

$f_{i,j}$ 会被 $f_{i, j - cost_{i}}$ 影响，相当于物品被选多次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int n, m;
cin >> n >> m;
vector<int> cost(n + 1), value(n + 1);
for(int i = 1; i <= n; i++){
    cin >> cost[i] >> value[i];
}

vector<int> f(m + 1);
for(int i = 1; i <= n; i++){
    for(int j = m; j >= cost[i]; j--){
        f[j] = max(f[j], f[j - cost[i]] + value[i]);
    }
}

cout << f[m];

完全背包

题意概要：有 $n$ 个物品和一个容量为 $v$ 的背包，每个物品有重量 $cost_{i}$ 和价值 $value_{i}$ 两种属性，要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量。(每个物品可选无限次)

先考虑朴素解：
$$
f_{i, j} = max(f_{i - 1, j - k \times cost_{i}} + k \times value_{i})
$$
复杂度可能达到 $O(n^{2} \times v)$

简单优化

可以发现，对于 $f_{i, j}$ ，只要通过 $f_{i, j - cost_{i}}$ 转移就可以了。因为状态转移方程为：
$$
f_{i, j - cost_{i}} = max(f_{i - 1, j - (k + 1) \times cost_{i}} + (k + 1) \times value_{i})
$$
对比上面转移方程只多了一个，我们通过局部最优子结构的性质重复使用了之前的枚举过程，优化了枚举的复杂度。
$$
f_{i, j} = max(f_{i - 1, j}, f_{i, j - cost_{i}} + value_{i})
$$

复杂度 $O(n \times v)$

main code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int m, n;
cin >> m >> n;
vector<int> cost(n + 1), value(n + 1);
for(int i = 1; i <= n; i++){
    cin >> cost[i] >> value[i];
}

vector<vector<int>> f(n + 1, vector<int>(m + 1));
for(int i = 1; i <= n; i++){
    for(int j = 0; j <= m; j++){
        if(j >= cost[i]){
            f[i][j] = max(f[i - 1][j], f[i][j - cost[i]] + value[i]);
        }else{
            f[i][j] = f[i - 1][j];
        }
    }
}

cout << f[n][m];

一维优化空间 $f_{j} = max(f_{j - cost_{i}})$ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int m, n;
cin >> m >> n;
vector<long long> cost(n + 1), value(n + 1);
for(int i = 1; i <= n; i++){
    cin >> cost[i] >> value[i];
}

vector<long long> f(m + 1);
for(int i = 1; i <= n; i++){
    for(int j = cost[i]; j <= m; j++){
        f[j] = max(f[j], f[j - cost[i]] + value[i]);
    }
}

cout << f[m];

发现与0-1背包方程一样， 这时候要正序枚举 $j$

多重背包

题意概要：有 $n$ 个物品和一个容量为 $v$ 的背包，每个物品有重量 $cost_{i}$ 和价值 $value_{i}$ 两种属性，要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量。(每个物品可选 $k_{i}$ )
$$
f_{i, j} = max(f_{i - 1, j - k \times cost_{i}} + k \times value_{i}) \quad if \quad k \le k_{i}
$$

二进制优化

将 $k_{i}$ 拆成 $1, 2, 4, …, 2^{p}, x$ （ $x$ 为剩下补足，范围 $0 \le x < 2^{p + 1}$ ），这样每个物品最多产生 $log_{2}(k_{i})$ 个物品

然后当成0-1背包即可

main code
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
int n, m;
cin >> n >> m;
vector<long long> v(n + 1), c(n + 1), k(n + 1);
for(int i = 1; i <= n; i++){
    cin >> v[i] >> c[i] >> k[i];
}

vector<long long> cost, value;
for(int i = 1; i <= n; i++){
    for(int j = 1; j < k[i]; k[i] -= j, j *= 2){
        cost.push_back(c[i] * j);
        value.push_back(v[i] * j);
    }
    cost.push_back(c[i] * k[i]);// 补足
    value.push_back(v[i] * k[i]);// 补足
}
n = cost.size();

vector<long long> f(m + 1);// 0-1 背包
for(int i = 0; i < n; i++){
    for(int j = m; j >= cost[i]; j--){
        f[j] = max(f[j], f[j - cost[i]] + value[i]);
    }
}

cout << f[m];

复杂度 $O(v \times \sum\limits_{i = 1}^{n} log_{2}(k_{i}))$

单调队列优化

$$
f_{i, j} = max(f_{i - 1, j - k \times cost_{i}} + k \times value_{i})
$$

设 $g_{i, x, y} = f_{i, x \times cost_{i} + y}$
$$
g_{i, x, y} = max(g_{i - 1, x - k, y} + k \times value_{i}) \quad if \quad k \le k_{i}
$$
设 $G_{i, x, y} = g_{i, x, y} - x \times cost_{i}$
$$
g_{i, x, y} = max(G_{i - 1, x - k, y}) + x \times cost_{i}
$$
可以看出 $g_{i, x, y}$ 由窗口 $[i - k, i - 1]$ 转移，滑动窗口问题求 $max$ 可用单调队列求取

main code
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
int n, m;
cin >> n >> m;
vector<long long> value(n + 1), cost(n + 1), k(n + 1);
for(int i = 1; i <= n; i++){
    cin >> value[i] >> cost[i] >> k[i];
}

vector<long long> f(m + 1);
for(int i = 1; i <= n; i++){
    auto g = f;// g 表示上一次状态
    for(int y = 0; y < cost[i]; y++){
        deque<long long> q;// 队列
        for(int x = y; x <= m; x += cost[i]){
            while(!q.empty() && q.front() < x - k[i] * cost[i]){
                q.pop_front();
            }

            if(!q.empty()){
                f[x] = max(f[x], g[q.front()] + (x - q.front()) / cost[i] * value[i]);
            }

            while(!q.empty() && g[q.back()] - (q.back() - y) / cost[i] * value[i] <= g[x] - (x - y) / cost[i] * value[i]){
                q.pop_back();
            }

            q.push_back(x);
        }
    }
}

cout << f[m];

复杂度 $O(n \times v)$

区间 $dp$

一般形式
$$
f_{l, r} = max(f_{l, k} + f_{k + 1, r} + cost)
$$

$n$ 堆石子，$a_1, a_2,…,a_n$ 每次合并相邻两堆，代价是两堆石子之和，求变为一堆的最小代价

main code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const int inf = 1e9;
int n;
cin >> n;
vector<int> val(n + 1), sum(n + 1);
for(int i = 1; i <= n; i++){
    cin >> val[i];
    sum[i] = sum[i - 1] + val[i];
}

vector<vector<int>> f(n + 1, vector<int>(n + 1, inf));
for(int i = 1; i <= n; i++){
    f[i][i] = 0;
}

for(int len = 1; len <= n; len++){
    for(int l = 1; l + len <= n; l++){
        int r = l + len;
        for(int k = l; k < r; k++){
            f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + sum[r] - sum[l - 1]);
        }
    }
}

cout << f[1][n];

树形 $dp$

$$
f_{u} = (f_v + …)
$$
即在父节点时考虑子节点

某大学有 $n$ 个职员，编号为 $1\ldots n$。

他们之间有从属关系，他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。

现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 $r_i$，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。求最大的快乐指数。

$f_u$ 表示包含 $u$ 的结果

$g_u$ 表示不包含 $u$ 的结果

main code

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
int n;
cin >> n;
vector<int> val(n + 1);
for(int i = 1; i <= n; i++){
    cin >> val[i];
}

int root = 0;
vector<vector<int>> relation(n + 1);
for(int i = 1; i < n; i++){
    int v, u;
    cin >> v >> u;
    relation[u].push_back(v);
    root ^= i ^ v;
}
root ^= n;

vector<int> f(n + 1);
vector<int> g(n + 1);
auto dp = [&](auto self, int u) -> void {
    f[u] = val[u];
    for(int& v : relation[u]){
        self(self, v);
        f[u] += g[v];
        g[u] += max(f[v], g[v]);
    }
};
dp(dp, root);

cout << max(f[root], g[root]);

数位 $dp$

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

数位 DP：用来解决一类特定问题，这种问题比较好辨认，一般具有这几个特征：

  1. 要求统计满足一定条件的数的数量（即，最终目的为计数）；
  2. 这些条件经过转化后可以使用「数位」的思想去理解和判断；
  3. 输入会提供一个数字区间（有时也只提供上界）来作为统计的限制；
  4. 上界很大（比如 $10^{18}$ )，暴力枚举验证会超时。

数位 $dp$ 经常与记忆化搜索一同出现

求区间计数一般转化为前缀 即求 $[l, r]$ 变为 $[0, r] - [0, l - 1]$

不含前导零且相邻两个数字之差至少为 $2$ 的正整数被称为 $windy$ 数。$windy$ 想知道，在 $l$ 和 $r$ 之间，包括 $l$ 和 $r$ ，总共有多少个 $windy$ 数？

$f_{i, j}$ 表示当前是第 $i$ 位，该位为 $j$ ，$windy$ 数的个数
$$
f_{i, j} = \sum\limits_{k = 0}^{9} f_{i - 1, k} \quad if \quad abs(j - k) \ge 2
$$

main code

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
const int N = 10;// 0 - 9 进制位
const int M = 12;// 数位 
long long f[M][N] = { 0 };
for(int i = 0; i < N; i++){
    f[0][i] = 1;
}

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

auto get = [&](long long x) -> long long {
    if(x == 0){
        return 0;
    }
    vector<int> digit;
    while(x != 0){
        digit.push_back(x % 10);
        x /= 10;
    }
    // 计算位数 = x 位数 的答案
    int last = -2;
    long long ans = 0;
    for(int i = digit.size() - 1; i >= 0; i--){
        for(int j = (i == digit.size() - 1); j < digit[i]; j++){// 最高位从一开始
            if(abs(j - last) >= 2){
                ans += f[i][j];
            }
        }

        if(abs(last - digit[i]) < 2){
            break;
        }
        last = digit[i];

        if(i == 0){//本身
            ans++;
        }
    }
    // 计算位数 < x 位数 的答案
    for(int i = 0; i < digit.size() - 1; i++){
        for(int j = 1; j <= 9; j++){
            ans += f[i][j];
        }
    }

    return ans;
};

long long l, r;
cin >> l >> r;
cout << get(r) - get(l - 1);

复杂度 $O(M \times N^{2})$

状压 $dp$

用二进制位来表示状态

需要用到位运算知识

在 $N \times N$ 的棋盘里面放 $K$ 个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 $8$ 个格子。

main code

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
int n, k;
cin >> n >> k;

auto get = [&](int x) -> int {
    int ans = 0;
    for(int i = 0; i < n; i++){
        if((x >> i) & 1){
            ans++;
        }
    }
    return ans;
};

vector<int> bits, cnts;
for(int i = 0; i < (1 << n); i++){ // 预处理每行可行状态
    if(((i >> 1) & i) == 0){ // 相邻位
        bits.push_back(i);
        cnts.push_back(get(i));
    }
}

auto check = [&](int j, int p) -> bool {
    if(j & p){
        return false;
    }

    if((j >> 1) & p){
        return false;
    }

    if(j & (p >> 1)){
        return false;
    }
    return true;
};

vector<vector<vector<long long>>> f(n + 2, vector<vector<long long>>(1 << n, vector<long long>(k + 1)));
f[0][0][0] = 1;
for(int i = 1; i <= n + 1; i++){
    for(int j = 0; j < bits.size(); j++){
        for(int p = 0; p < bits.size(); p++){
            for(int c = 0; c <= k; c++){
                if(check(bits[j], bits[p]) && c + cnts[j] <= k){
                    f[i][bits[j]][c + cnts[j]] += f[i - 1][bits[p]][c];
                }
            }
        }                
    }
}

cout << f[n + 1][0][k];

$dp$ 优化

数据结构优化

单调栈优化

当 $dp$ 需要前一个 $or$ 后一个， 大于（等于） $or$ 小于（等于）它数列的状态时，可以考虑单调栈

给你一个数组 $[p_1, p_2, \dots, p_n]$ ，其中所有元素都是不同的。

你可以对它进行几个（可能是零）操作。在一个操作中，你可以选择 $p$ 的一个连续的子段，并从该子段中删除所有元素，除该子段中最小的元素。例如，如果是 $p = [3, 1, 4, 7, 5, 2, 6]$ ，你选择了从 $3$ -rd元素到 $6$ -th元素的子段，那么得到的数组就是 $[3, 1, 2, 6]$ 。

如果数组 $a$ 可以通过上述几种（也许是零种）操作从 $p$ 中得到，那么这个数组 $a$ 就叫做可达数组。计算可达数组的个数，并打印出它的模数 $998244353$ 。

$f_i$ 表示考虑前 $i$ 个数，不以第 $i$ 项结尾的个数

$g_i$ 表示考虑前 $i$ 个数，并以第 $i$ 项结尾的个数

考虑 $f_{i}$ 的转移， 因为不以第 $i$ 项结尾，前面必有比他小的数来删除它
$$
f_{i} = \sum\limits_{j = 0 \vee p_i > p_j }^{i - 1} g_{j}
$$
考虑前一个小于它的数， 记为 $p_{l[i]}$

对于 $p_j < p_{l[i]} < p_i$ 的 $g_j$ ， $p_{l[i]}$ 被 $p_{j}$ 删除，此时即 $f_{l[i]}$， 根据公式 $f_{l[i]} = \sum\limits_{j = 0 \vee p_{l[i]} > p_j }^{l[i] - 1} g_{j}$，而区间 $[l[i], i - 1]$ 没有小于 $p_i$ 的数，贡献为 $0$

对于 $p_i > p_j > p_{l[i]}$ 的 $g_j$ ， $p_{l[i]}$ 未被 $p_{j}$ 删除，此时即 $g_{l[i]}$，会以 $p_{l[i]}$ 结尾
$$
\sum\limits_{j = 0 \vee p_i > p_j }^{i - 1} g_{j} = f_{l[i]} + g_{l[i]}
$$

考虑 $g_i$ 的转移，以第 $i$ 项结尾，那它可以删除大于它的项，保留第一个小于它的项
$$
g_{i} = \sum\limits_{j = l[i]}^{i - 1} g_{j} + f_{l[i]}
$$
该式 $\sum\limits_{j = l[i]}^{i - 1} g_{j}$ 可用前缀和计算

main code
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
const int mod = 998244353;
int n;
cin >> n;
vector<int> val(n + 1);
for(int i = 1; i <= n; i++){
    cin >> val[i];
}

vector<int> l(n + 1);
vector<int> stk = { 0 };
for(int i = 1; i <= n; i++){
    while(!stk.empty() && val[i] < val[stk.back()]){
        stk.pop_back();
    }
    l[i] = stk.back();
    stk.push_back(i);
}

vector<long long> f(n + 1), g(n + 1), sum(n + 1);
g[0] = 1;
sum[0] = 1;
for(int i = 1; i <= n; i++){
    if(l[i]){
        f[i] = (f[l[i]] + g[l[i]]) % mod;
        g[i] = (f[l[i]] + sum[i - 1] - sum[l[i] - 1]) % mod;
    }else{
        g[i] = (f[l[i]] + sum[i - 1]) % mod;
    }

    sum[i] = (sum[i - 1] + g[i]) % mod;
}

cout << ((f[n] + g[n]) % mod + mod) % mod << "\n";

单调队列优化

有 $n$ 座烽火台，每个烽火台发出信号都有代价。在连续 $m$ 个烽火台中至少要有一个发出信号。计算最少的代价。

$f_{i}$ 表示考虑前 $i$ 个，并且在 $i$ 设立的最小代价

根据题意
$$
f_{i} = min(f_{j} + cost_{i}) \quad if \quad i - j \le m
$$
即一个大小为 $m$ 的滑动窗口， 求最值，用队列维护

设队头为最优值

当窗口离开它时，队头出列

当新值优于队尾时，队尾出列

加入新值

main code
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
const int inf = 1e9;
int n, m;
cin >> n >> m;
vector<int> cost(n + 1);
for(int i = 1; i <= n; i++){
    cin >> cost[i];
}

int ans = inf;
deque<int> q = { 0 };
vector<int> f(n + 1, inf);
f[0] = 0;
for(int i = 1; i <= n; i++){
    while(!q.empty() && i - q.front() > m){
        q.pop_front();
    }

    f[i] = min(f[i], f[q.front()] + cost[i]);

    while(!q.empty() && f[i] <= f[q.back()]){
        q.pop_back();
    }

    q.push_back(i);

    if(n - i < m){
        ans = min(ans, f[i]);
    }
}
cout << ans;

线段树/树状数组优化

$dp$ 需要区间状态的某些性质时，可以考虑线段树/树状数组优化

斜率优化

一般形式
$$
f_{i} = min(f_{j} + a_{i} \times b_{i}) \quad if \quad j < i
$$

四边形不等式优化

四边形不等式

对于任何 $a \le b \le c \le d$ 均有 $f(a, c) + f(b, d) \le f(a, d) + f(b, c)$

则称 $f$ 满足四边形不等式

还是石子合并那题

用 $p_{l, r}$ 记录分割点，优化决策

main code

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
const int inf = 1e9;
int n;
cin >> n;
vector<int> val(n + 1), sum(n + 1);
for(int i = 1; i <= n; i++){
    cin >> val[i];
    sum[i] = sum[i - 1] + val[i];
}

vector<vector<int>> p(n + 2, vector<int>(n + 2));
vector<vector<int>> f(n + 2, vector<int>(n + 2, inf));
for(int i = 1; i <= n; i++){
    f[i][i] = 0;
    p[i][i] = i;
}

for(int delta = 1; delta < n; delta++){
    for(int l = 1; l + delta <= n; l++){
        int r = l + delta;
        for(int k = p[l][r - 1]; k <= p[l + 1][r]; k++){
            if(f[l][r] > f[l][k] + f[k + 1][r] + sum[r] - sum[l - 1]){
                f[l][r] = f[l][k] + f[k + 1][r] + sum[r] - sum[l - 1];
                p[l][r] = k;
            }
        }
    }
}

cout << f[1][n];

复杂度 $O(n^{2})$