背包问题

01背包

每个物品只能拿一次，求拿容量不超过V的物品能得到的最大价值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int n, m;
int v[N], w[N];
int f[N];
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    for(int i = 1; i <= n; i++)
        for(int j = m; j >= v[i]; j--)
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    cout << f[m];
    return 0;
}

完全背包

每个物品可以使用无数次，求拿容量不超过V的物品能得到的最大价值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int v[N], w[N];
int f[N];
int n, m;
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    for(int i = 1; i <= n; i++) 
        for(int j = v[i]; j <= m; j++)//与01背包代码唯一不同的地方
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    cout << f[m];
    return 0;
}

多重背包

每个物品只能拿一次，每个物品最多有s件，求拿总容量不超过V的物品能得到的最大价值

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
#include <bits/stdc++.h>
using namespace std;
const int N = 12010;
int v[N], w[N];
int n, m;
int f[N];
int main()
{
    cin >> n >> m;
    int cnt = 0;
    for(int i = 1; i <= n; i++) 
    {
        int a, b, s;
        cin >> a >> b >> s;
        int k = 1;
        while(k <= s)
        {
            cnt++;
            v[cnt] = a * k, w[cnt] = b * k;
            s -= k, k *= 2;
        }
        if(s > 0)
        {
            cnt++;
            v[cnt] = a * s, w[cnt] = b * s;
        }
    }
    n = cnt;
    for(int i = 1; i <= n; i++)
        for(int j = m; j >= v[i]; j--)
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    cout << f[m];
    return 0;
}

分组背包

每组有若干个物品，每组只能选一个物品，求拿总容量不超过V的物品能得到的最大价值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int f[N];
int v[N][N], w[N][N], s[N];
int n, m;
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> s[i];
        for(int j = 1; j <= s[i]; j++) cin >> v[i][j] >> w[i][j];
    }
    for(int i = 1; i <= n; i++)
        for(int j = m; j >= 0; j--)
            for(int k = 0; k <= s[i]; k++)
                if(v[i][k] <= j)    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
    cout << f[m];
    return 0;
}

线性Dp

数字三角形

方式一：从上往下“走”

  1. 状态表示：\(f(i, j)\)
    • 集合：从\((1, 1)\)到\((i, j)\)的所有情况
    • 属性：MAX
  2. 状态计算
    • 这条路可以从\(f(i - 1, j)\)走上来，也可以从\(f(i-1,j-1)\)走上来
    • 所以，\(f(i,j)=max(f(i-1,j),f(i-1,j-1))+g(i,j)\)
  3. 答案：根据定义答案就是\(max(f[n][i])\)

\(\color{Red}{注意：}\)因为存在边界的情况，所以需要初始化为\(-\infty\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
const int N = 510;
int g[N][N], f[N][N];
int n;
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= i; j++)
            cin >> g[i][j];
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= i + 1; j++)
            f[i][j] = -1e9;
    f[1][1] = g[1][1];
    for(int i = 2; i <= n; i++)
        for(int j = 1; j <= i; j++)
            f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + g[i][j];
    int ans = -0x3f3f3f3f;
    for(int i = 1; i <= n; i++)
        ans = max(ans, f[n][i]);
    cout << ans;
    return 0;
}

方式二：从下往上“走”

  1. 状态表示：\(f(i,j)\)
    • 集合：从\((i,j)\)到\((1,1)\)
    • 属性：MAX
  2. 状态计算
    • 这条路可以从\(f(i+1,j)\)走上来，也可以从\(f(i+1,j+1)\)走上来
    • \(f(i,j)=max(f(i+1,j),f(i+1,j+1))+g(i,j)\)
  3. 答案：\(f(1,1)\)

\(\color{red}{注意：}\)因为是从下往上的遍历，边界都包括在内，不用考虑边界情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
const int N = 510;
int g[N][N], f[N][N];
int n;
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= i; j++)
            cin >> g[i][j];
    for(int i = n; i >= 1; i--)
        for(int j = 1; j <= i; j++)
            f[i][j] = max(f[i + 1][j], f[i + 1][j + 1]) + g[i][j];
    cout << f[1][1];
    return 0;
}

最长上升子序列

方式一：时间复杂度\(O(n^2)\)

  1. 状态表示：\(f(i)\)
    • 集合：表示以\(w[i]\)结尾的最大上升子序列
    • 属性：MAX
  2. 状态计算
    • 以i之前的、权值小于i的节点结尾的上升子序列的最大值 + 1
    • \(f(i) = max(f(j)+1)\)，其中\(w[j]<w[i],j<i\)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
const int N = 1010;
int w[N], f[N];
int n, ans;
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> w[i];
    for(int i = 1; i <= n; i++)
    {
        f[i] = 1;
        for(int j = 1; j <= i; j++)
            if(w[i] > w[j]) f[i] = max(f[i], f[j] + 1);//找到以比w[i]小的节点结尾的最长上升子序列
        ans = max(ans, f[i]);
    }
    cout << ans;
    return 0;
}

方式二：时间复杂度\(O(nlogn)\)

  1. 状态表示\(f(i)\)
    • 集合：表示长度为i的序列的最小结尾
    • 属性：序列中最后一个值的最小值
  2. 状态计算：
    • 如果\(w[i]\)大于\(f(cnt)\)，直接加到cnt之后即可
    • 如果小于等于\(f(cnt)\)，找到f数组中第一个大于\(w[i]\)的位置，进行替换
  3. 答案：f数组的长度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int w[N], f[N];
int n, cnt;
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> w[i];
    f[++cnt] = w[1];//初始化
    for(int i = 2; i <= n; i++)
    {
        if(w[i] > f[cnt]) f[++cnt] = w[i];
        else f[lower_bound(f + 1, f + cnt + 1, w[i]) - f] = w[i];
    }
    cout << cnt;
    return 0;
}

最长公共子序列

状态表示：\(f(i,j)\)

  1. 集合：表示A的前i个字符，B的前j个字符的公共子序列的最长长度
  2. 属性：min

状态计算：

  1. \(a[i] == b[j]\)，\(a[i],b[j]\)都在，那么最长子序列的长度是前一个 + 1，即\(f[i-1][j-1]+1\)
  2. \(a[i]!=b[j]\)
    • \(a[i]\)在，\(b[j]\)不在：那就是算A的前i个字符，B的前i - 1个字符的公共子序列的最长长度，即\(f[i][j - 1]\)
    • \(a[i]\)不在，\(b[j]\)在：那就是算A的前i - 1个字符，B的前i个字符的公共子序列的最长长度，即\(f[i-1][j]\)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
char a[N], b[N];
int n, m;
int f[N][N];
int main()
{
    cin >> n >> m >> a + 1 >> b + 1;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            if(a[i] == b[j])
                f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
        }
    cout << f[n][m];
    return 0;
}

最短编辑距离

状态表示：\(f(i,j)\)

  1. 集合：表示\(A[1\sim i]\)转换到\(B[1\sim j]\)最少操作次数
  2. 属性：min

状态计算：

  1. 删：保证\(A[1\sim i-1]\)和\(B[1\sim j]\)匹配，即\(f[i-1][j]\)
  2. 替：保证\(A[1\sim i-1]\)和\(B[1\sim j-1]\)匹配，即\(f[i-1][j-1]\)
  3. 补：保证\(A[1\sim i]\)和\(B[1\sim j-1]\)匹配，即\(f[i][j-1]\)

总结：\(f[i][j] = min(f[i-1][j-1]+1,f[i-1][j]+1,f[i][j-1]+1)\)

初始化：

  1. \(f[0][i]\)只能进行”补“操作
  2. \(f[i][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
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
char a[N], b[N];
int n, m;
int f[N][N];

int main()
{
    cin >> n >> a + 1 >> m >> b + 1;
    memset(f, 0x3f, sizeof f);
    for(int i = 0; i <= n; i++) f[i][0] = i;
    for(int i = 0; i <= m; i++) f[0][i] = i;
    
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
            //if(a[i] != b[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
            //else f[i][j] = min(f[i][j], f[i - 1][j - 1]);
            f[i][j] = min(f[i][j], f[i - 1][j - 1] + (a[i] != b[j]));
        }
        
    cout << f[n][m];
    return 0;
}

区间Dp

石子合并

状态表示：\(f(i, j)\)

  1. 集合：表示合并区间从i到j的最小代价
  2. 属性：min（记得初始化为\(\infty\)）

状态计算：

  1. 涉及区间和问题，使用前缀和

  2. \(f(i,j) = f(i,k)+f(k+1,j)+s[j]-s[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
#include <iostream>
using namespace std;
const int N = 310;
int f[N][N], a[N];
int n;
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i], a[i] += a[i - 1];
    
    for(int len = 2; len <= n; len++)
    {
        for(int i = 1; i + len - 1 <= n; i++)
        {
            int j = i + len - 1;
            f[i][j] = 0x3f3f3f3f;
            for(int k = i; k <= j; k++)
            {
                f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + a[j] - a[i - 1]);
            }
        }
    }
    cout << f[1][n];
    return 0;
}

计数类Dp

整数划分

分析：可以看成完全背包问题的变式，把1,2,3，……，n看做n个物品，每个物品可以取无限次，问刚好取到体积为n的方案数

状态表示：f(i, j)

  1. 集合：表示前i个物品体积恰好为j的方案数
  2. 属性：所有相加

状态计算：

\(f(i,j) = f(i-1,j)+f(i-1,j-i)+f(i-1,j-2i),……\)

\(f(i,j-i)=f(i-1,j-i)+f(i-1,j-2i)+f(i-1,j-3i)+……\)

\(\to\)\(f(i,j)=f(i-1,j)+f(i,j-i)\)

省去第一维：\(f(j)=f(j)+f(j-i)\)

初始化：

当一件都不选的时候方案数是1，所以\(f[0]=1\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int f[N];
int n;
int main()
{
    cin >> n;
    f[0] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = i; j <= n; j++)
            f[j] = (f[j] + f[j - i]) % mod;
    cout << f[n];   
    return 0;
}

数位统计Dp

计数问题

分析：

  1. 将\(a\sim b\)中\(1\sim9\)出现的次数转换成\(1\sim a-1\)和\(1\sim b\)中每个数字出现的次数

  2. 对于求abcdefg中t在第4位出现的次数

    例子：1 <= xxxtyyy <= abcdefg

    1. xxx = 0 ~ abc - 1, yyy = 000 ~ 999，次数：abc * 1000
    2. xxx = abc
      1. d == t，yyy = 000 ~ efg ，次数：efg + 1
      2. d > t，yyy = 000 ~ 999，次数：10^3
      3. d < t，不成立

  3. 对于t 是否等于0，如果是0，它不可能在首位，在算某一位数前面的xxx的时候，需要减去前面全是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
59
60
#include <bits/stdc++.h>
using namespace std;
const int N = 1e8 + 10;
int num[N];
int get_num(int l, int r)
{
    int res = 0;
    for(int i = l; i >= r; i--)
        res = res * 10 + num[i];
    return res;
}
int pow10(int x)
{
    int ans = 1;
    for(int i = 1; i <= x; i++)
        ans *= 10;
    return ans;
}
int work(int n, int x)
{
    if(n == 0) return 0;
    int len = 0, ans = 0;
    while(n)
    {
        num[++len] = n % 10;
        n /= 10;
    }
    if(x != 0)
    for(int i = len; i > 0; i--)
    { 
        if(i != len) ans += get_num(len, i + 1) * pow10(i - 1);
        if(num[i] == x) ans += get_num(i- 1, 1) + 1;
        else if(num[i] > x) ans += pow10(i - 1);
        else ans += 0;
    }
    else
    for(int i = len - 1; i > 0; i--)
    {
        ans += (get_num(len, i + 1) - 1) * pow10(i - 1);
        if(num[i] == x) ans += get_num(i- 1, 1) + 1;
        else if(num[i] > x) ans += pow10(i - 1);
        else ans += 0;
    }
    return ans;
}
int main()
{
    int a, b;
    while(scanf("%d%d", &a, &b) && a !=0 && b != 0)
    {
        if(a > b) swap(a, b);
        for(int i = 0; i <= 9; i++)
        {
            int ans = work(b, i) - work(a - 1, i);
            cout << ans << " ";
        }
        cout << '\n';
    }
    return 0;
}

状态压缩Dp

充分利用二进制

蒙德里安的梦想

分析：一旦横着摆放的地方确定了，那么竖着摆放的地方就确定了。所以，最终的方案数就是横着摆放的方案数

状态表示：\(f(i,j)\)

  1. 我们按照列进行摆放，每一列由上一列更新
  2. 状态数：每一列的某行为1，表示横放，并伸出到下一列；某行为0，表示竖放或者由上一列伸出
  3. \(f(i,j)\)表示第i行，状态数为j时的方案数；其中状态数j是01组成的二进制数

状态计算：

  1. \(f(i,j)=\sum f(i-1,k)\)表示第i-1列的所有合法方案数之和
  2. 初值：\(f[0][0] = 1\)，第0列没有横放的
  3. 答案：\(f[m][0]\)

判断是否合法：

  1. 上一列横放伸出的地方为1，那么这一列的这一行只能是0，即j & k == 0
  2. 连续零的个数是偶数

提前初始化：

  • 根据上述两个规则初始化st数组，将所有状态是否合法列举出来
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;
const int N = 12, M = 1 << N;
typedef long long ll;
ll f[N][M];
bool st[M];
int n, m;
ll work(int n, int m)
{
    //预处理
    for(int i = 0; i < 1 << n; i++)
    {
        st[i] = true;
        int cnt = 0;//记录每一列中连续0的个数
        for(int j = 0; j < n; j++)
        {
            if(i >> j & 1)
            {
                if(cnt & 1)
                {
                    st[i] = false;
                    break;
                }
            }
            else cnt++;
        }
        if(cnt & 1) st[i] = false;//判断前导零
    }
    //状态计算
    memset(f, 0, sizeof f);
    f[0][0] = 1;
    for(int i = 1; i <= m; i++)//枚举列
        for(int j = 0; j < 1 << n; j++)//枚举第i列的状态
            for(int k = 0; k < 1 << n; k++)//枚举第i-1列的状态
                if((j & k) == 0 && st[j | k]) f[i][j] += f[i - 1][k];
    return f[m][0];
}
int main()
{
    while(cin >> n >> m, n | m)
    {
        cout << work(n, m) << '\n';
    }
    return 0;
}

最短Hamilton路径

状态表示：\(f(state,j)\)

  1. 集合：终点为j，路径状态为state的距离；一共有20个点，以二进制形式进行表示，共有\(2^{20}\)个情况
  2. 属性：min

状态计算：

  1. \(0\to j\) 可以转换成 \(0\to k\to j\)

  2. \(0\to k\)就是从state中减去j的路径情况

  3. 合法性判断：state减去j之后的路径中第k位是否是1，如果是则合法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
const int N = 20, M = 1 << N;
int f[M][N], w[N][N];
int n;
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cin >> w[i][j];
    memset(f, 0x3f, sizeof f);
    f[1][0] = 0;
    for(int i = 0; i < 1 << n; i++)
        for(int j = 0; j < n; j++)
            if(i >> j & 1) 
                for(int k = 0; k < n; k++)
                    if(((i - (1 << j)) >> k) & 1)
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
    cout << f[(1 << n) - 1][n - 1];          
    return 0;
}

树形Dp

状态表示是\(f[N][2]\)

没有上司的舞会

状态表示：

  1. \(f(i,1)\)表示在以i为根节点的子树中选择并且选择i
  2. \(f(i,0)\)表示在以i为根节点的子树中选择并且不选择i

状态计算：\((i,j)\)

  1. 对于\(f(i,1)\)，显然不能选择j，所以\(f(i,1)+=f(j,0)\)
  2. 对于\(f(i,0)\)，j可选可不选，所以\(f(i,0)+=max(f(j,0),f(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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
const int N = 6010, M = 2 * N;
int head[M], ne[M], to[M], idx;
int happy[N];
bool fa[N];
int f[N][2];
int n;
void add(int a, int b)
{
    ne[idx] = head[a], to[idx] = b, head[a] = idx++;
}
void dfs(int r)
{
    f[r][1] += happy[r];
    for(int i = head[r]; i != -1; i = ne[i])
    {
        int j = to[i];
        dfs(j);
        f[r][1] += f[j][0];
        f[r][0] += max(f[j][0], f[j][1]);
    }
}
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> happy[i];
    memset(head, -1, sizeof head);
    for(int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        add(b, a);
        fa[a] = b;
    }
    int root = 1;
    while(fa[root]) root++;
    dfs(root);
    cout << max(f[root][0], f[root][1]);
    return 0;
}

记忆化搜索

滑雪

状态表示：\(f(i,j)\)

  1. 集合：表示最终滑到\((i,j)\)的一条路径

  2. 属性：max

状态计算：

  • 分成\(f(i-1,j)+1,f(i,j-1)+1,f(i+1,j)+1,f(i,j+1)+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
#include <bits/stdc++.h>
using namespace std;
const int N = 310;
int n, m;
int g[N][N],f[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int dp(int x, int y)
{
    int &v = f[x][y];//用v代替f[x][y]方便
    if(v != -1) return v;
    v = 1;//注意把v变成1
    for(int i = 0; i < 4; i++)
    {
        int xx = x + dx[i], yy = y + dy[i];
        if(xx > 0 && xx <= n && yy > 0 && yy <= m && g[x][y] > g[xx][yy])
            v = max(v, dp(xx, yy) + 1);
    }
    return v;
}
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> g[i][j];
    int res = 0;
    memset(f, -1, sizeof f);        
    for(int i = 1; i <= n; i++)//因为每个点都可能是起点，所以都需要加入
        for(int j = 1; j <= m; j++)
            res = max(res, dp(i, j));
    cout << res ;
    return 0;
}