notes

Appearance

动态规划 ​

动态规划的解题步骤 ​

  1. 确定dp数组（dp table）以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

动态规划基础 ​

最长公共子序列 ​
  1. 表示 和 的最长公共子序列长度
  2. 递推公式：
  3. dp数组初始化：如果下标从 开始，则
  4. 遍历顺序：从左到右，从上到下

c++代码实现：

cpp
vector<vector<int>> dp(n + 1, vector<int>(m + 1));
for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= m; j++) {
        if(a[i] == b[j]) {
            dp[i][j] = dp[i-1][j-1] + 1;
        }else {
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }
}
最长非递减子序列 ​
  1. 定义原序列为 ， 为长度为 的非递减子序列的末尾元素的最小值, 为当前非递减子序列的长度
  2. 考虑进来一个元素 :
    • 如果 ，则将该元素放进 序列末尾,
    • 如果 ，则找到 中第一个大于等于 的元素，将其替换为
  3. 初始化：, (下标从 开始)
  4. 遍历顺序：从左到右

c++代码实现：

cpp
vector<int> d(n, INT_MAX);
d[0] = a[0];
int len = 0;
for(int i = 1; i < n; i++) {
    if(a[i] >= d[len]) {
        d[++len] = a[i];
    }else {
        *upper_bound(d.begin(), d.end(), a[i]) = a[i];
    }
}
len++;

若求严格递增子序列，则将 改为 , upper_bound 改为 lower_bound

背包问题 ​

01背包 ​
  1. 定义 为前 件物品放入容量为 的背包中能获得的最大价值
  2. 递推公式：
  3. dp数组初始化：如果下标从 开始，则 ，

c++代码实现：

cpp
int c, n;
cin >> c >> n;
vector<int> w(n), v(n);
for(int i = 0; i < n; i++) {
    cin >> w[i];
}
for(int i = 0; i < n; i++) {
    cin >> v[i];
}

vector<vector<int>> dp(n + 1, vector<int>(c + 1, 0));
for(int i = 1; i <= n; i++) { // 先遍历物品
    for(int j = 0; j <= c; j++) { // 再遍历背包容量
        if(j < w[i]) {
            dp[i][j] = dp[i-1][j];
        }else {
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
        }
    }
}
cout << dp[n][c] << endl;

也可以先遍历背包容量，再遍历物品，代码如下：

一维DP数组（滚动数组）

如果把 那一层拷贝到 上，表达式完全可以是：

与其把 这一层拷贝到 上，不如只用一个一维数组了，只用 （一维数组，也可以理解是一个滚动数组）。

一维dp数组的递推公式： ;

cpp代码实现：

cpp
int c, n;
cin >> c >> n;
vector<int> w(n), v(n);
for(int i = 0; i < n; i++) {
    cin >> w[i];
}
for(int i = 0; i < n; i++) {
    cin >> v[i];
}

vector<int> dp(n + 1, vector<int>(c + 1, 0));
for(int i = 1; i <= n; i++) { // 先遍历物品
    for(int j = c; j >= w[i]; j--) { // 再遍历背包容量
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
}
cout << dp[c] << endl;

注意：一维dp数组的遍历顺序是从后往前遍历背包容量，防止重复计算同一物品的价值。

状压DP ​

位运算基础 ​
  • 去掉最后一位：x >> 1
  • 最后一位加一个0：x << 1
  • 最后一位加一个1：x << 1 | 1
  • 把最后一位变成1：x | 1
  • 把最后一位变成0：x & ~1 、 (x | 1) - 1
  • 最后一位取反：x ^ 1
  • 把右数第k位变成1：x | (1 << (k - 1))
  • 把右数第k位变成0：x & ~(1 << (k - 1))
  • 右数第k位取反：x ^ (1 << (k - 1))
  • 取末k位：x & ((1 << k) - 1)
  • 取右数第k位：(x >> (k - 1)) & 1
  • 把末k位变成1：x | ((1 << k) - 1)
  • 末k位取反：x ^ ((1 << k) - 1)
  • 把右边连续的1变成0：x & (x + 1)
  • 把右边连续的0变成1：x | (x - 1)
  • 把右起的第一个0变成1：x | (x + 1)
  • 把右起的第一个1变成0：x & (x - 1)
  • 取右边连续的1：(x ^ (x + 1)) >> 1
  • 去掉右起第一个1的左边：x & (-x)
牛客NC20240 - 互不侵犯 ​

题目描述

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

输入描述

只有一行，包含两个数N，K （ 1 ≤ N ≤ 9, 0 ≤ K ≤ N * N）

输出描述

方案数。

C++代码

cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int num[600];
ll dp[10][100][600]; // [行][国王数][状态] 的方案数

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> st;
    for(int i = 0; i < (1 << n); i++) {
        if(i & (i << 1))    continue;
        st.push_back(i); // 存一行中合法的状态(同一行的国王不能互相攻击)
        int x = i;
        while(x) {
            num[i] += x & 1; // 存该状态的国外数
            x >>= 1;
        }
    }
    dp[0][0][0] = 1;
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= k; j++) {
            for(auto sti : st) { // 遍历第i行的状态
                if(num[sti] > j)    continue;
                for(auto last : st) { // 遍历上一行的状态
                    if(num[sti] + num[last] > j)    continue;
                    // 判断第i行与上一行的状态是否冲突
                    if(last & sti)    continue;
                    if((last << 1) & sti)    continue;
                    if((last >> 1) & sti)    continue;
                    dp[i][j][sti] += dp[i-1][j - num[sti]][last];
                }
            }
        }
    }
    
    ll ans = 0;
    for(auto i : st) {
        ans += dp[n][k][i];
    }
    cout << ans << endl;
    
    return 0;
}