【动态规划】状态压缩DP
前言
二进制的很多应用离不开集合这个概念，我们都知道在计算机当中，所有数据都是以二进制的形式存储的。一般一个 int 整形是 4 个字节，也就是 32 位 bit，我们通过这 32 位 bit 上 0 和 1 的组合可以表示多大 21 亿个不同的数。如果我们把这 32 位 bit 看成是一个集合，那么每一个数都应该对应集合的一种状态，并且每个数的状态都是不同的。那么我们可不可以用一个数来保存一维的 DP 状态呢？
这当然是可行的，动态规划的过程是随着阶段的增长，在每一个状态维护上不断扩展的。而对于某些题目，我们扩展时需要记录一个状态集合，保存状态信息，以便进行状态转移。而状态压缩则是把这一个大小不超过 N、元素小于 K 的集合看做是一个 N 位的 K 进制数，以一个$[0, K^N - 1]$之间的十进制整数的形式作为 DP 状态的一维。这样我们就可以只用一个十进制整数，就保存了一个状态信息——这就是状态压缩。
状态压缩的题目一般只有两种状态（当然也有三种状态的
集合操作
在二进制状态 DP 中，我们用一个十进制整数代表一个集合，例如：$9 -> (1001)_{2}$ ，可以等效替换为一个 bool 数组$B[4] = {1, 0, 0, 1}$。下面是集合的常用操作：
| 操作含义 | 代码 | | :abbrlink: 122ed47c mathjax: true categories:
● OI 学习笔记
● 动态规划 pubDate: 2023-06-10 00:00:00 tags:
● 优化
● 状态压缩
● DP
● 动态规划
● cpp
● OI title: 【动态规划】状态压缩 DP badge: old
----------------------
-----------------------------------: | :----------------: | | 取出整数 n 在二进制表示下的第 k 位 | (n >> k) & 1 | | 取出整数 n 在二进制表示下的第 0k-1 位（后 k 位） | n & ((1 << k) - 1) | | 把整数 n 在二进制下表示的第 k 位取反 | n ^ (1 << k) | | 对整数 n 在二进制表示下的第 k 位赋值 1 | n| (1 << k) | | 对整数 n 在二进制表示下的第 k 位赋值 0 | n & ( (1 << k)) | | 判断整数 n 在二进制表示下的第 k 位是否为真 | n & (1 << (k - 1)) |
上机实践
售货员的难题
构思（朴素算法）
看一下题目……最短路是吧？但是要求经过所有结点。
所以优先队列 BFS 最短路这种就不管用啦！那么既然要走过所有村庄，直接枚举全排列输出，暴力省事。时间复杂度为$O(N * N!)$，属于是必死无疑。
下面给出一段基础搜索代码，包含基础剪枝，得分$80Pt$.
via サン猫の時間漂流
前言
二进制的很多应用离不开集合这个概念，我们都知道在计算机当中，所有数据都是以二进制的形式存储的。一般一个 int 整形是 4 个字节，也就是 32 位 bit，我们通过这 32 位 bit 上 0 和 1 的组合可以表示多大 21 亿个不同的数。如果我们把这 32 位 bit 看成是一个集合，那么每一个数都应该对应集合的一种状态，并且每个数的状态都是不同的。那么我们可不可以用一个数来保存一维的 DP 状态呢？
这当然是可行的，动态规划的过程是随着阶段的增长，在每一个状态维护上不断扩展的。而对于某些题目，我们扩展时需要记录一个状态集合，保存状态信息，以便进行状态转移。而状态压缩则是把这一个大小不超过 N、元素小于 K 的集合看做是一个 N 位的 K 进制数，以一个$[0, K^N - 1]$之间的十进制整数的形式作为 DP 状态的一维。这样我们就可以只用一个十进制整数，就保存了一个状态信息——这就是状态压缩。
状态压缩的题目一般只有两种状态（当然也有三种状态的
三进制题目）。这里只讨论最常见的二进制状态压缩，K 进制状态压缩可以以此类推，不再赘述。集合操作
在二进制状态 DP 中，我们用一个十进制整数代表一个集合，例如：$9 -> (1001)_{2}$ ，可以等效替换为一个 bool 数组$B[4] = {1, 0, 0, 1}$。下面是集合的常用操作：
| 操作含义 | 代码 | | :abbrlink: 122ed47c mathjax: true categories:
● OI 学习笔记
● 动态规划 pubDate: 2023-06-10 00:00:00 tags:
● 优化
● 状态压缩
● DP
● 动态规划
● cpp
● OI title: 【动态规划】状态压缩 DP badge: old
----------------------
-----------------------------------: | :----------------: | | 取出整数 n 在二进制表示下的第 k 位 | (n >> k) & 1 | | 取出整数 n 在二进制表示下的第 0k-1 位（后 k 位） | n & ((1 << k) - 1) | | 把整数 n 在二进制下表示的第 k 位取反 | n ^ (1 << k) | | 对整数 n 在二进制表示下的第 k 位赋值 1 | n| (1 << k) | | 对整数 n 在二进制表示下的第 k 位赋值 0 | n & ( (1 << k)) | | 判断整数 n 在二进制表示下的第 k 位是否为真 | n & (1 << (k - 1)) |
注意了！我们常说的第一位在二进制表示下其实是第零位，程序实现时一定要注意当前真正在操作的是哪一位，否则 WA 了很难找出错误。
上机实践
售货员的难题
经典例题，状态压缩 DP 入门题：P1171 售货员的难题。
构思（朴素算法）
看一下题目……最短路是吧？但是要求经过所有结点。
所以优先队列 BFS 最短路这种就不管用啦！那么既然要走过所有村庄，直接枚举全排列输出，暴力省事。时间复杂度为$O(N * N!)$，属于是必死无疑。
下面给出一段基础搜索代码，包含基础剪枝，得分$80Pt$.
#include<cstdio>
using namespace std;
int lxy[21][21],hrb[21];
int n,i,j,k,minn=1e9;
int ss(int x,int y,int z)//x表示村子编号，y表示走了几个村子，z表示用的时间
{
if(z > minn) return 0;//基本最小值剪枝
if(y == n && z + lxy[x][1] < minn)
{
minn = z + lxy[x][1];
return 0;
}//比较求最小值，其中的加lxy[x][1]意思是走回第一个村
for(int i = 2; i <= n; i++)//循环开始
{
if(hrb[i]==0&&i!=x)//深搜模板，没走就搜
{
hrb[i] = 1;//打上标记
ss(i,y + 1, z + lxy[x][i]);
hrb[i] = 0;//回溯
}
}
return 0;
}
int main()
{
scanf("%d", &n);
for(i = 1;i <= n; i++)
for(k = 1;k <= n; k++)
scanf("%d", &lxy[i][k]);//输入
ss(1, 1, 0);//开搜
printf("%d",minn);
}
via サン猫の時間漂流
【动态规划】LIS与LCS（最长上升子序列）
引子-LIS 问题
这几天在学习DP（动态规划），里面第一个接触到的问题就是LIS问题，这里简单概述如下:
----------------------
LIS 的朴素解法
最朴素的想法就是用一个数组$DP[i]$表示在$1-i$范围内的 LIS 长度，初始化$DP[i]$为$1$（它自己一个数作为一个 LIS）。如果在小于$1-i$的范围内有满足 LIS 定义的情况，就可以转移$DP[i]$的值，代表选入这个范围和$A[i]$做为 LIS 的一部分。
我们要遍历到$DP[i]$时同时遍历所有在$1-i$内的状态，显然每次转移都是$O(N)$的时间复杂度，总复杂度为$O(N^2)$，状态转移方程如下：
$DP[i] = max(DP[i], DP[j] + 1) | (j < i)$
显然$O(N^2)$的时间复杂度是无法满足 OIer 的，因此我们要进行优化。
----------------------
LIS 的贪心二分优化
优化思路
为什么朴素算法慢呢？因为我们把所有情况枚举了一遍，而最后留下的只有一种。LIS 的朴素算法在那些本不需要枚举的状态上浪费了时间，自然就不行了。
我们知道，LIS 是一个严格单增的数列，那么在两个 LIS 长度相同的情况下，我们希望它能扩展到的长度尽可能长，自然是希望LIS 结尾元素尽可能小。那么思路就有了，我们使用一个数组$G[i]$保存长度为$i$的 LIS 的结尾元素值记录当前最长的 LIS 长度为$tot$，对于每一个$A[i]$，如果$A[i] > G[tot]$，说明当前可以把$A[i]$接到这一条所谓最长的 LIS 后面，则$G[++tot] = A[i]$。
那么我们的问题就是如何维护$G$数组。其实很简单，思路就是我们上面的思路，但是有一个问题，如果$A[i] \leq G[tot]$，应该怎么办呢？
那么根据我们的优化思路，我们要尽可能确保当前$G$数组里面存储的是当前长度为$i$的 LIS 序列的最优解，也就是
二分优化
显然，$G$数组是一个单调递增的数组，自然地可以使用二分查找优化时间复杂度。把时间复杂度降到$O(N,log,N)$级别。
代码整合
那么到目前为止，我们亲爱的$DP$数组就寿终正寝了，换成了我们新的$G$数组（
下面是代码示例，基础 LIS：
LIS 例题
这里给出一道 LIS 模板题：导弹拦截 LIS 经典。
将拦截的导弹的高度提出来成为原高度序列的一个子序列，根据题意这个子序列中的元素是单调不增的（即后一项总是不大于前一项），我们称为单调不升子序列。本问所求能拦截到的最多的导弹，即求最长的单调不升子序列。（其实只要判断改一下就好啦！）
第一问
没什么好说的，跑一次示例代码完事。
第二问
那么既然是单调不升子序列，我们考虑朴素算法，那么$G$数组就要求存储最大的值，每次执行完一次计算，就把选中的元素移除。重复计算，直到全部移除，记录计算次数，输出为答案。
但是这样显然太笨了！我们要优化优化优化！
我们不妨改变一下$G$数组的含义，用$G[i]$存第$i$个系统当前能够拦截的高度，同时我们把这些系统按从小到大排列——类似于原来的$G$数组。显然每次遍历到导弹$A[i]$时，我们拿最小的$G[i] \geq A[i]$是最优解。然后更新$G[i]$的值，显然更新之后排列还是从小到大，$G$数组仍然是单调递增的，因此不需要重新排序。当然如果没有满足$G[i] \geq A[i]$的情况，就新增一个系统。
只要我们仍然保存时间复杂度在$O(N,log,N)$ 级别，可以通过$10^5$的数据。
代码整合
下面是 AC 代码：
via サン猫の時間漂流
引子-LIS 问题
这几天在学习DP（动态规划），里面第一个接触到的问题就是LIS问题，这里简单概述如下:
给定一个长度为$N$的数列$A$，求数值单调递增的子序列的的长度最长是多少？其中 LIS（最长上升子序列）指的是从序列 A 中选择若干个 i，使得$i_{1}<i_{2}<i_{3}...<i_{n}$的同时满足$A_{i_{1}}<A_{i_{2}}<A_{i_{3}}...<A_{i_{n}}$。
----------------------
LIS 的朴素解法
最朴素的想法就是用一个数组$DP[i]$表示在$1-i$范围内的 LIS 长度，初始化$DP[i]$为$1$（它自己一个数作为一个 LIS）。如果在小于$1-i$的范围内有满足 LIS 定义的情况，就可以转移$DP[i]$的值，代表选入这个范围和$A[i]$做为 LIS 的一部分。
我们要遍历到$DP[i]$时同时遍历所有在$1-i$内的状态，显然每次转移都是$O(N)$的时间复杂度，总复杂度为$O(N^2)$，状态转移方程如下：
$DP[i] = max(DP[i], DP[j] + 1) | (j < i)$
显然$O(N^2)$的时间复杂度是无法满足 OIer 的，因此我们要进行优化。
----------------------
LIS 的贪心二分优化
优化思路
为什么朴素算法慢呢？因为我们把所有情况枚举了一遍，而最后留下的只有一种。LIS 的朴素算法在那些本不需要枚举的状态上浪费了时间，自然就不行了。
我们知道，LIS 是一个严格单增的数列，那么在两个 LIS 长度相同的情况下，我们希望它能扩展到的长度尽可能长，自然是希望LIS 结尾元素尽可能小。那么思路就有了，我们使用一个数组$G[i]$保存长度为$i$的 LIS 的结尾元素值记录当前最长的 LIS 长度为$tot$，对于每一个$A[i]$，如果$A[i] > G[tot]$，说明当前可以把$A[i]$接到这一条所谓最长的 LIS 后面，则$G[++tot] = A[i]$。
那么我们的问题就是如何维护$G$数组。其实很简单，思路就是我们上面的思路，但是有一个问题，如果$A[i] \leq G[tot]$，应该怎么办呢？
那么根据我们的优化思路，我们要尽可能确保当前$G$数组里面存储的是当前长度为$i$的 LIS 序列的最优解，也就是
结尾元素尽可能小的情况。所以我们要在$G$数组中找到第一个大于$A[i]$的元素$G[j]$，用$A[i]$更新$G[i]$。可是如果单纯遍历，复杂度又双叒叕回到了$O(N^2)$级别，所以……
二分优化
显然，$G$数组是一个单调递增的数组，自然地可以使用二分查找优化时间复杂度。把时间复杂度降到$O(N,log,N)$级别。
代码整合
那么到目前为止，我们亲爱的$DP$数组就寿终正寝了，换成了我们新的$G$数组（
什么NTR剧情）。下面是代码示例，基础 LIS：
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#define MAX 100005
#define INF 1e9
using namespace std;
int A[MAX]; //存数字
int G[MAX]; //我们亲爱的G数组
int tot = 1;
int main()
{
int N = 0; //长度
for(int i = 1; i <= N; i++)
{
scanf("%d", &A[i]);
G[i] == INF; //初始化为1e9
}
G[1] = A[1]; //我们开始的起点
for(int i = 2; i <= N; i++)
{
if(A[i] > G[tot]) //只要能插入，就先插入
G[++tot] = A[i]; //初始化最后一个元素值
else
{
int l = 1, r = tot, mid; //新建变量
while (l < r)
{
//基础二分查找
mid = (l + r) >> 1;
if(G[mid] > A[i]) r = mid;
else l = mid + 1;
}
G[l] = min(G[l], A[i]); //赋值，加MIN保险
}
}
printf("%d", tot); //输出答案
return 0;
}
LIS 例题
这里给出一道 LIS 模板题：导弹拦截 LIS 经典。
将拦截的导弹的高度提出来成为原高度序列的一个子序列，根据题意这个子序列中的元素是单调不增的（即后一项总是不大于前一项），我们称为单调不升子序列。本问所求能拦截到的最多的导弹，即求最长的单调不升子序列。（其实只要判断改一下就好啦！）
第一问
没什么好说的，跑一次示例代码完事。
注意这里$G$数组递减！请修改二分查找！
第二问
那么既然是单调不升子序列，我们考虑朴素算法，那么$G$数组就要求存储最大的值，每次执行完一次计算，就把选中的元素移除。重复计算，直到全部移除，记录计算次数，输出为答案。
但是这样显然太笨了！我们要优化优化优化！
我们不妨改变一下$G$数组的含义，用$G[i]$存第$i$个系统当前能够拦截的高度，同时我们把这些系统按从小到大排列——类似于原来的$G$数组。显然每次遍历到导弹$A[i]$时，我们拿最小的$G[i] \geq A[i]$是最优解。然后更新$G[i]$的值，显然更新之后排列还是从小到大，$G$数组仍然是单调递增的，因此不需要重新排序。当然如果没有满足$G[i] \geq A[i]$的情况，就新增一个系统。
只要我们仍然保存时间复杂度在$O(N,log,N)$ 级别，可以通过$10^5$的数据。
代码整合
下面是 AC 代码：
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define MAX 100005
#define INF 1e9
using namespace std;
int A[MAX]; //存数字
int G[MAX]; //我们亲爱的G数组
int tot = 1;
int main()
{
int N = 0; //长度
while(~scanf("%d",&A[++N])); --N;
G[1] = A[1]; //我们开始的起点
for(int i = 2; i <= N; i++)
{
if(A[i] <= G[tot]) //只要能插入，就先插入
G[++tot] = A[i]; //初始化最后一个元素值
else
{
int l = 1, r = tot, mid;
while (l < r)//获得下标，注意这里G数组递减
{
//基础二分查找
mid = (l + r) >> 1;
if(G[mid] >= A[i]) l = mid + 1;
else r = mid;
}
G[l] = max(G[l], A[i]); //赋值，加MAX保险
}
}
printf("%d\n", tot); //输出答案一
//重置数据
tot = 1;
memset(G, INF, sizeof(G));
G[1] = A[1];
for(int i = 2; i <= N; i++)
{
int l = 1, r = tot, mid;
while (l < r)//获得下标，当然也可能没有
{
//基础二分查找
mid = (l + r) >> 1;
if(G[mid] >= A[i]) r = mid;
else l = mid + 1;
}
if(G[l] >= A[i]) G[l] = A[i]; //如果找得到，赋值
else G[++tot] = A[i]; //如果找不到，初始化一个新的系统
}
printf("%d\n", tot); //输出答案二
return 0;
}
via サン猫の時間漂流
隐说 No.8 真正的危险在于仍用过去的逻辑做事
1、转型警惕路径依赖 “动荡时代最大的危险不是动荡本身，而是仍然用过去的逻辑做事” —— 彼得·德鲁克 太隐识：转型的根本在于转变底层逻辑，如果底层逻辑没有改变，仍然是过去的传统形式，那么又何谈改变呢。那么被历史和市场淘汰也是可以预料的事情了。 2、参禅 真正的参禅，也重在作务，重在生活。百丈禅师说：“搬柴运水，无非是禅；扬眉瞬目，无非是道。”因此，真正的禅是什么？搬柴运水是禅，腰石舂米是禅，犁田锄草是禅，早耕晚课是禅，忍耐慈悲是禅，劳苦牺牲是禅，方便灵巧是禅，棒喝教化是禅。......
READ MORE
via 太隐 (author: Ludwig Wang)
1、转型警惕路径依赖 “动荡时代最大的危险不是动荡本身，而是仍然用过去的逻辑做事” —— 彼得·德鲁克 太隐识：转型的根本在于转变底层逻辑，如果底层逻辑没有改变，仍然是过去的传统形式，那么又何谈改变呢。那么被历史和市场淘汰也是可以预料的事情了。 2、参禅 真正的参禅，也重在作务，重在生活。百丈禅师说：“搬柴运水，无非是禅；扬眉瞬目，无非是道。”因此，真正的禅是什么？搬柴运水是禅，腰石舂米是禅，犁田锄草是禅，早耕晚课是禅，忍耐慈悲是禅，劳苦牺牲是禅，方便灵巧是禅，棒喝教化是禅。......
READ MORE
via 太隐 (author: Ludwig Wang)
Next.js + Vite，这是什么新的操作？
事情是这样的。
前段日子做了一个摄影佬必备的线上图库。
https://github.com/Afilmory/Afilmory
这个项目是 Vite + React 写的，当初没有考虑要做 SEO 的打算。
然后想给
那用什么呢，不管用什么必须的支持 Serverless，毕竟我也不想多开一个服务器去托管了。
现在支持 Serverless 的太多，hono，fastify 都可以。我最后还是选择了 Next.js。一开始只想着它处理和画 OG 最方便，而且可以直接托管到 Cloudflare Pages 上。
目前，已知我的 app 是 SPA，vite build 之后是静态产物。我需要在 Next.js 上托管这些静态产物。
托管静态产物，这还不简单。我直接一个
但是，index.html 的
我直接用 dom 操作替换一下。
那么就搞定了对 HTML 的处理，注入了 OG 相关的 Meta 标签。
这里有个注意，截止到这边文章编写前，在使用 Cloudflare Pages 部署 Next.js app 仍有不少问题。比如这里的 fetch 可能导致报错 Cannot perform Construct on a detached ArrayBuffer。我现在的方案就是不适用 fetch。而是在 build 阶段转换为 js 文件。
OK，这样就搞定了。后面开发还是可以用 SPA 去开发，部署的时候去部署 Next.js。直接通过 Cloudflare Pages 一键部署就行了。
看完了？说点什么呢
via 静かな森 (author: Innei)
该渲染由 Shiro API 生成，可能存在排版问题，最佳体验请前往：https://innei.in/posts/Z-Turn/nextjs%2Bvite-hack-combined
事情是这样的。
前段日子做了一个摄影佬必备的线上图库。
https://github.com/Afilmory/Afilmory
这个项目是 Vite + React 写的，当初没有考虑要做 SEO 的打算。
然后想给
/:photoId 路由加个 Open Gragh 的支持。那必须得上一个 Server 了。那用什么呢，不管用什么必须的支持 Serverless，毕竟我也不想多开一个服务器去托管了。
现在支持 Serverless 的太多，hono，fastify 都可以。我最后还是选择了 Next.js。一开始只想着它处理和画 OG 最方便，而且可以直接托管到 Cloudflare Pages 上。
目前，已知我的 app 是 SPA，vite build 之后是静态产物。我需要在 Next.js 上托管这些静态产物。
托管静态产物，这还不简单。我直接一个
vite build && cp -r dist ../ssr/public。放到 public 下就被 Next.js 自动托管了。但是，index.html 的
<head /> 咋办，vite build 出来的都是死的。我直接用 dom 操作替换一下。
import { DOMParser } from 'linkedom'
export const runtime = 'edge'
export const GET = async (
request: NextRequest,
{ params }: { params: Promise<{ photoId: string }> },
)
try {
const indexHtml = await fetch(new URL('./index.html', import.meta.url)).then(r => r.text())
const document = new DOMParser().parseFromString(indexHtml, 'text/html')
// Remove all twitter meta tags and open graph meta tags
document.head.childNodes.forEach((node) => {
if (node.nodeName === 'META') {
const $meta = node as HTMLMetaElement
if ($meta.getAttribute('name')?.startsWith('twitter:')) {
$meta.remove()
}
if ($meta.getAttribute('property')?.startsWith('og:')) {
$meta.remove()
}
}
})
// Insert meta open graph tags and twitter meta tags
createAndInsertOpenGraphMeta(document, photo, request)
return new Response(document.documentElement.outerHTML, {
headers: {
'Content-Type': 'text/html',
'X-SSR': '1',
},
})
} catch (error) {
console.error('Error generating SSR page:', error)
console.info('Falling back to static index.html')
console.info(error.message)
return new Response(indexHtml, {
headers: { 'Content-Type': 'text/html' },
status: 500,
})
}
}那么就搞定了对 HTML 的处理，注入了 OG 相关的 Meta 标签。
这里有个注意，截止到这边文章编写前，在使用 Cloudflare Pages 部署 Next.js app 仍有不少问题。比如这里的 fetch 可能导致报错 Cannot perform Construct on a detached ArrayBuffer。我现在的方案就是不适用 fetch。而是在 build 阶段转换为 js 文件。
# Convert HTML to JS format with exported string
node -e "
const fs = require('fs');
const html = fs.readFileSync('./public/index.html', 'utf8');
const jsContent = \`export default \\\`\${html.replace(/\`/g, '\\\\\`').replace(/\\\$/g, '\\\\\$')}\\\`;\`;
fs.writeFileSync('./src/index.html.ts', jsContent);
"OK，这样就搞定了。后面开发还是可以用 SPA 去开发，部署的时候去部署 Next.js。直接通过 Cloudflare Pages 一键部署就行了。
后续
Cloudflare Pages 免费版本的 Worker CPU Time 限制的太低了，而生成 OG 的事件远超这个需要的时间，导致 OG 生成经常不可用。现在使用 Railway 去部署了。
看完了？说点什么呢
via 静かな森 (author: Innei)
