2023.8.4 学习笔记

常规
1

状压DP & 数位DP

状压DP 集合式

  • 即加半维描述状态，按二进制将状态压缩到一维里，常来记录一个点是否被访问

  • 若那半维为0/1/2，可手动改成三进制状压

  • 位运算小寄巧：

  • 1.取出整数s二进制从低到高第k位的数

    (s >> (k - 1)) & 1

  • 2.取出整数s二进制从低到高的前k(1 ~ k)位的数

    s & ((1 << k) - 1)

  • 3.将s二进制第k位取反

    s ^ (1 << (k - 1))

  • 4.将s二进制第k位赋成1

    s | (1 << (k - 1))

典型例题

eg1:旅行商问题(哈密顿回路)

  • 设f[i][s]为当前i在每个点的访问状态为s时的最小路程，s的第i位为0/1 代表 第i座城市没有/已经访问过
  • 规定出发点为i
  • 如：11001 → 1,4,5号城市被访问过
  • 初始化：f[i][0]=0
  • 结束状态：f[i][(1 << n) - 1]
  • 转移时枚举要走的边 设边长为v 通向$next_i$节点 则
   if(s&(1<<(next[i]-1))==0)
   f[next[i][s|(1<<(next[i]-1))]=min(f[next[i]][s|(1<<(next[i]-1))],f[i][s]+v)

eg2:关键点问题

  • 首先跑k+1遍Dijkstra预处理出起点和k个点到所有点的最短路，这样可以O(1)查询每个关键点到其他点的最短距离进行转移
  • 状压存储k个关键点是否被访问过
  • 转移时枚举下一个要去的未访问关键点，或者当所有关键点均被访问时的状态+当前点到点1的距离来更新状态
  • 转移方程f[next[i]][s|(1<<next[i])]=min(f[next[i][s|(1<<next[i])],f[i][s]+dis[i][next[i]])
  • 答案为f[1][(1<<k)-1]

eg3:带权无向图中走完所有边再回到起点的最小代价(正权，有重边)

  • 先floyd预处理出点对之间两两最小距离
  • 考虑"每条边至少被经过一遍"的信息
  • 若原图为欧拉图，则答案为边权之和
  • 若原图不是欧拉图，将重新经过的路径视为加边，加最小代价的边，使原图变成欧拉图
  • 将新加的边连的两个点度数+1，使得最终每个点的度数为偶数
  • 对于最优方案，每条完整新增路径两端一定连接两个奇度数顶点
  • 提取出所有奇度数点进行状压DP,获得多跑的长度
  • 记录0为奇，1为偶
  • 每次枚举两个点，以两点间的最短路径长度作为代价更新状态即可

[000100110000] + dis[1][8] → [000110110001]

  • dp[s]->dp[s|(1<<(i-1))|(1<<(j-1))]
  • 最终状态:dp[111111…11111111]
  • ans = 多跑的长度 + 原图的边权和

eg4:愤怒的小鸟

  • 按小猪死没死作为状态
  • dp[s] s的第i位是0/1 → 是否为死猪 死为1 没死为0 此时花费的最小小鸟
  • 预处理line[i][j]代表的是经过i号猪和j号猪的抛物线，他的击杀情况(0110010)
  • 转移方程：
    dp[s|line[i][j]]=min{dp[s]+1}
    dp[s|(1<<(k-1))]=min{dp[s]+1}
  • BUT 会TLE
  • 直接钦定：每次一定打编号最小的没死的猪
  • 编号最小的即为最低位的0，但是这不太好求，怎么办呢？
  • 重新定义死为0 没死为1 编号最小的猪即为lowbit(s)
  • 然后枚举另一维，转移
  • 直接优化个n，拿下此题

状压DP 棋盘式

eg4:互不侵犯

  • dp[i][j][k]表示决策到第i行 已经用了j个王 当前行的状态为s时的方案数
  • 有限制(t为非s行的状态)即
   s & t == 0
   s & (t >> 1) == 0
   s & (t << 1) == 0
   s & (s >> 1) == 0
   s & (s << 1) == 0
  • dp[i][j][s2]+=dp[i-1][j-cnt[s2]][s1] 其中s1 , s2满足限制
  • 初始化：dp[0][0][0] = 1

数位DP

  • 一般用于统计范围内满足某特征的数字个数
  • 考虑按位枚举，用dp统计已经填了某些位、满足某些要求的方案数

eg5:windy数

  • 需求分解：
  • 1.不含前导0
  • 2.相邻两个数字之差至少为2
  • 3.在A到B之间
  • 统计A到B之间的数字个数cnt[A][B]=cnt[1][B]-cnt[1][A-1]
  • dp[i][j]代表对于一个i位数(从低到高)，最高位的数码为j时，windy数的个数，且这个i位数满足相邻两数之差>=2
  • dp[i+1][j]=\sum{dp[i][k]}(|k-j|>=2)
  • 合法情况：(num[i]即为上界的位数,共k位)
  • 1.位数比上界还要小 ans+=dp[1...k-1][1...9](√)
  • 2.位数相同，最高位小于上界的最高位 ans+=dp[k][1...num[k]-1](√)
  • 3.位数相同，最高位也相同 (√)
    for(i=k-1...i)
    	if num[i]相同
    		ans+=dp[i][0...num[i]-1];

代码(递推式)(以不变应万变)：

#include <bits/stdc++.h>
using namespace std;
#define int long long
int dp[15][15];
int num[15];
int calc(int x)
{
    int len = 0;
    while (x > 0ll) // 获得其位数与各位上的数码
        num[++len] = x % 10, x /= 10;
    int sum = 0ll;
    for (int i = 1; i <= len - 1; i++) // case 1:位数小
        for (int j = 1; j <= 9; j++)
            sum += dp[i][j];
    for (int i = 1; i <= num[len] - 1; i++) // case 2:位数同，最高位小
        sum += dp[len][i];
    for (int i = len - 1; i >= 1; i--) // case 3:位数同，最高位同
    {
        for (int j = 0; j <= num[i] - 1; j++) // 从高往低扫
            if (abs(j - num[i + 1]) >= 2)
                sum += dp[i][j];
        if (abs(num[i + 1] - num[i]) < 2) // 因为搜到这一位时，说明前几位都与上界相同，如果上界不合法，那我们相同的那几位也不合法
            break;                        // 这一位不行后面的位子一定不行
    }
    return sum;
}
signed main()
{
    int n, m;
    scanf("%lld %lld", &n, &m);
    if (n > m)
        swap(n, m);
    for (int i = 0; i <= 9; i++)
        dp[1][i] = 1ll;

    /*预处理dp*/
    for (int i = 2; i <= 10; i++)
        for (int j = 0; j <= 9; j++)
            for (int k = 0; k <= 9; k++)
                if (abs(k - j) >= 2)
                    dp[i][j] += dp[i - 1][k];

    printf("%lld\n", calc(m + 1) - calc(n));
    return 0;
}

代码(递归式)(思路简单，代码易变)：

#include <bits/stdc++.h>
using namespace std;
int dp[507][507];
int num[507];
int dfs(int pos, int pre, int flag, int nozero)
// 从高往低，还剩pos位没有决策（没有填数），前一位上的数是pre，当前是不是在卡上界，前导零的问题是否（1/0）已被解决
// 前导零的问题？见PPT
{
    /*一些可以直接返回的情况*/
    int tot = 0;
    if (pos == 0) // 搜到底，这是一个可行的windy数，返回1
        return 1;
    if (flag == 0 && dp[pos][pre] != -1 && nozero)
    // 目前不在卡上界，前导零的问题也已被解决，则返回记忆化的结果
    {
        return dp[pos][pre];
    }

    /*处理出数码枚举的上限*/
    int lim;  // 数码枚举的上限
    if (flag) // 卡上界中
        lim = num[pos];
    else
    {
        lim = 9; // 上限是9，任取
    }

    /*枚举填什么，并往不同的方向转移*/
    for (int i = 0; i <= lim; i++) // 枚举这一位该填啥
    {
        int ABS = abs(i - pre);
        if (ABS >= 2 || !nozero) // 若前导零的问题还没被解决，则不要受到前面的0的限制
        {
            if (i == lim && flag) // 依然卡上界
            {
                tot += dfs(pos - 1, i, 1, 1);
            }
            else
            {
                if (i != 0 || nozero) // 前导零的问题已经解决
                {
                    tot += dfs(pos - 1, i, 0, 1);
                }
                else // 前导零的问题还在继续！
                {
                    tot += dfs(pos - 1, i, 0, 0);
                }
            }
        }
    }

    /*记忆化*/
    if (!flag && nozero) // 记忆化
    {
        dp[pos][pre] = tot;
    }
    return tot;
}
int calc(int x)
{
    memset(dp, -1, sizeof(dp));
    int k = 0;
    while (x) // 提取位数和每位上的数
    {
        num[++k] = x % 10;
        x /= 10;
    }
    return dfs(k, 0, 1, 0);
}
int main()
{
    int L, R;
    cin >> L >> R;
    cout << calc(R) - calc(L - 1) << endl;
}

eg6:数字计数

  • dp[i][j][k]表示一个i位数，最高位是j，k数码的次数
  • 转移方程(递推式)
  • dp[i][j][k]+=\sum dp[i-1][0..9][k]
  • dp[i][j][j]+=10^{i-1}
  • 递归式由于笔者不喜欢(懒得写)，在此不作解释
2 个赞