浅い夏よ 終わってくれよ
淡薄的夏啊 为我画下句点吧
8月28日
高中第一日。晚上吃完饭去弹琴了。弹完到操场向天边望去，深蓝之中点缀着几抹血红。晚霞真好看呐。
晚课，dyx和lyd小朋友由于无事可做，用笔记纸手写了线段树。考虑到其纪念意义，它被贴在了机房黑板上，与ljx的手印享有同等地位。
8月29日
晚上又去弹琴了。可惜今天并没有晚霞呢。
8月30日 & 状压DP
集训一日，主要训练状压DP。上午其他人进行了S组模拟赛，下午开始颓，内容包括但不限于配置steam、使用Beep函数演奏《春日影》、联机配置bongo cat等。
特此感谢zhw送来的蜜雪冰城。
1.概念
状压DP，即状态压缩动态规划，是动态规划的分支。
这类算法通常通过将某一状态集合转化为一串k进制整数来记录状态，进而进行状态转移等操作。大多数问题中，k=2，即用一串n位二进制数来表示含有n个元素的状态集合。注意，这里状态集合中的元素有顺序之分。
通过状态压缩，可以简便地实现遍历状态、访问状态、判断状态是否可行等复杂操作。这类操作的代码实现一般要使用位运算。
状压DP的时间复杂度一般为\(O(n^22^n)\)，数据范围一般为\(N≤21\)。
2.例题
(1) P1896 [SCOI2005] 互不侵犯
状压经典例题。
可以用一串二进制数存储每一行国王的状态，0表示空格子，1表示放国王。例如，串010100表示在这一行，第2、4个格子放了国王，其余格子留空的一种状态。这种状态对应一个十进制整数24。
如何判断某一行的状态是否可行呢？可以考虑到，如果串s的某一位是1，那么它左边的和右边的位都不能是1。所以我们可以设计出判断算法：当((s<<1)&s)==0 && ((s>>1)&s)==0 成立时，串s才合法。
这样做的原因是：把串s位移一位，与原来的串s按位与之后，若存在位为1的情况，则说明某位的左边或右边存在国王。进而说明，当且仅当根据上述规则计算出的两个串等于0时，串s才合法。
简单地，可以写成：(((s<<1)|(s>>1))&s)==0。
可以维护一个数组st，用于存储所有合法的状态串。
容易想到状态定义：f[i][j][s]表示已经放了i行，用了j个国王，第i行的状态为s的放置方案数。
显然有f[i][j][s1]+=f[i-1][j-cnt[s1]][s2]，s1是目前状态，s2是先前状态，当且仅当j-cnt[s1]>=0，且s2与s1“互不侵犯”，即((s2|(s2<<1)|(s2>>1))&s1)==0。
最后，答案为f[n][k][st[i]]的累加。
边界显然是f[0][0][0]=1，因为不放也是一种方案。
code:
#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int N=2000;
int n,K,st[N],cnt[N],stnum,ans,f[10][100][N];
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>K;for(int s=0;s<(1<<n);s++){//枚举所有可能状态，从全是0到全是1int tot=0,s1=s;while(s1){if(s1&1){tot++;}s1>>=1;}cnt[s]=tot;if((((s<<1)|(s>>1))&s)==0){//保证如果第j格放国王，第j-1和j+1都没有国王st[++stnum]=s;}}f[0][0][0]=1;for(int i=1;i<=n;i++){//枚举棋盘行数for(int j=1;j<=stnum;j++){for(int k=1;k<=stnum;k++){//枚举现在的和先前的状态int s1=st[j],s2=st[k];if(((s2|(s2<<1)|(s2>>1))&s1)==0){for(int l=0;l<=K;l++){//枚举国王个数if(l-cnt[s2]>=0){f[i][l][s2]+=f[i-1][l-cnt[s2]][s1];}}}}}}for(int i=1;i<=stnum;i++){ans+=f[n][K][st[i]];}cout<<ans;return 0;
}
(2) P1433 吃奶酪
直接暴力搜索只能得50pts，直接跑最短路好像也得不全分。故考虑状压。
先用两点距离公式预处理任意两点间的距离，记得存双向。
定义状态f[i][j]表示走到第i个奶酪，走过的奶酪状态为j时最短的距离。
首先枚举二进制状态，再枚举奶酪，如果当前奶酪对应的二进制位为1，则枚举另一个奶酪，如果与先前的奶酪不是同一个点，且这个奶酪对应的二进制位为0，则转移状态。
易得方程为：f[i][k]=min(f[i][k],f[j][k^(1<<(i-1))]+a[i][j])。
边界是从原点直接到i点，距离就是原点到i点的距离。
答案显然是f[i][(1<<n)-1]的最小值。
切记开double，存双向图，赋极大值。
code:
#include <bits/stdc++.h>
#define min(a,b) (((a)<(b))?(a):(b))
using namespace std;
int n;
struct Node{double x,y;
}v[20];
double dp[18][34000],dist[20][20];
double getd(int a,int b){return sqrt((v[a].x-v[b].x)*(v[a].x-v[b].x)+(v[a].y-v[b].y)*(v[a].y-v[b].y));
}
int main(){double ans=1e9;memset(dp,127,sizeof dp);cin>>n;for(int i=1;i<=n;i++){cin>>v[i].x>>v[i].y;}v[0]=Node{0,0};for(int i=0;i<=n;i++){for(int j=i+1;j<=n;j++){dist[i][j]=getd(i,j);dist[j][i]=dist[i][j];}}for(int i=1;i<=n;i++){dp[i][(1<<(i-1))]=dist[0][i];}for(int k=1;k<(1<<n);k++){for(int i=1;i<=n;i++){if((k&(1<<(i-1)))==0)continue;for(int j=1;j<=n;j++){if(i==j)continue;if((k&(1<<(j-1)))==0)continue;dp[i][k]=min(dp[i][k],dp[j][k-(1<<(i-1))]+dist[i][j]);}}}for(int i=1;i<=n;i++){ans=min(ans,dp[i][(1<<n)-1]);}printf("%.2f\n",ans);return 0;
}
(3) P2704 [NOI2001] 炮兵阵地
状压DP。
状态定义非常难想，因为某一行的状态跟前两行都有关系，所以不妨把当前行和前一行的状态都融入状态定义中。
定义f[i][s1][s2]表示枚举到第i行，上一行的状态是s1，当前行的状态是s2时（注意顺序），最多能摆放炮兵的数量
读入地图时，可将某一行的地图状态压缩为一个二进制串，即一维数组存地图，方便之后的二进制位运算。山地的位置存1。
打表记录。st[i]表示第i个状态，cnt[i]表示第i个状态中1的个数。
首先初始化边界。关于某一行所有的状态，必须保证：0 0 1 0 0，即某炮兵位置的左两位和右两位都没有炮兵，即若所枚举的状态为st，则必有(((st<<1)|(st<<2)|(st>>1)|(st>>2))&st)==0，再存到数组中，有点类似“互不侵犯”。
关于第一行，如果st&map[1]==0那么说明这一格是平原，可以放炮兵，则有f[1][0][st]=num（num为正在增长的合法状态个数）。
由于状态定义中融入了两行的状态，所以必须初始化前两行，才能接着推状态。
关于第二行，枚举第一行的状态st1和第二行的状态st2，转移时必须保证(st1 & st2)==0（st2所放的炮兵不能被st1放好的炮兵攻击。值得注意的是，炮兵的攻击范围是一个十字，与国王不同，这样转移就行）且(st2 & map[2])==0（平原）。
第二行的转移方程显然是f[2][st1][st2]=max(f[1][0][st1]+cnt[st2])。
接下来开始DP。枚举行数i，从3开始，到n结束。枚举当前行的状态st0，如果是平原，则再枚举前一行状态st1，如果当前行状态不与前一行状态冲突，则枚举前两行（指当前行往前数的第二行）的状态st2，如果前两行不与前一行和当前行冲突，则：f[i][st1][st0]=max(f[i-1][st2][st1]+cnt[st0])。
最后计算答案。最后两行为倒数第一、第二行的状态为答案状态，枚举这种状态统计答案，算出最大值即可。
补充1：这里我用了一个类似lowbit的1计数写法，比较简便（虽然内置库更简便）。
补充2：需要特判n=1时的特殊情况，否则hack点WA。
code:
#include <bits/stdc++.h>
using namespace std;
int getcnt(int x){int tot=0;while(x){tot++;x-=x&(-x);//类似lowbit思想}return tot;
}
const int M=105,N=1005;
int n,m,ans,num,s[N],cnt[N],f[M][N][N],a[M];
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m;if(n==1){//特判，存疑for(int i=1;i<=m;i+=3){ans++;}cout<<ans;return 0;}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){char c;cin>>c;if(c=='H'){a[i]|=(1<<(j-1));}}}for(int st=0;st<(1<<m);st++){if((((st<<1)|(st<<2)|(st>>1)|(st>>2))&st)==0){num++;s[num]=st;cnt[num]=getcnt(st);if((st&a[1])==0){//f的二三维传的是状态编号，而非二进制状态串本身，这样可以节省不必要的空间f[1][0][num]=cnt[num];}}}for(int st1=1;st1<=num;st1++){for(int st2=1;st2<=num;st2++){if((s[st1]&s[st2])||(s[st2]&a[2]))continue;f[2][st1][st2]=max(f[2][st1][st2],f[1][0][st1]+cnt[st2]);}}for(int i=3;i<=n;i++){//行数for(int st0=1;st0<=num;st0++){if(a[i]&s[st0])continue;for(int st1=1;st1<=num;st1++){if(s[st1]&s[st0])continue;for(int st2=1;st2<=num;st2++){if((s[st2]&s[st1])||(s[st2]&s[st0]))continue;f[i][st1][st0]=max(f[i][st1][st0],f[i-1][st2][st1]+cnt[st0]);}}}}for(int st1=1;st1<=num;st1++){for(int st2=1;st2<=num;st2++){ans=max(f[n][st1][st2],ans);}}cout<<ans;return 0;
}
(4) P1171 售货员的难题
旅行商DP，著名的NP完全问题，没有多项式解法，比较好的解法是状压。
定义f[st][i]表示已走过城市的状态为st，现在走到城市i的最短路径。
显然要为f赋初始最大值。
枚举状态st、当前的城市i，当f[st][i]有值时，枚举下一个城市j，当(st & (1<<(j-1)))==0，即城市j所属的位置在串st中的值为0时，转移状态。
状态转移方程显然是：f[st | (1<<(j-1))][j]=min(f[st][i]+a[i][j])。
值得注意的是，当串st中的全部二进制位都为1时，售货员不一定停在哪个城市，所以答案是f[1<<(n-1)][i]+a[i][1]中的最小值，其中i为城市序号的遍历。
code:
#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int N=21,M=1<<21;
int n,ans=(1<<30),a[N][N],f[M][N];
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);memset(f,0x3f,sizeof(f));cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>a[i][j];}}f[1][1]=0;for(int st=1;st<(1<<n);st++){for(int i=1;i<=n;i++){if(f[st][i]>=ans)continue;for(int j=1;j<=n;j++){if(st&(1<<(j-1)))continue;f[st|(1<<(j-1))][j]=min(f[st|(1<<(j-1))][j],f[st][i]+a[i][j]);}}}for(int i=2;i<=n;i++){ans=min(ans,f[(1<<n)-1][i]+a[i][1]);}cout<<ans;return 0;
}
(5) P1441 砝码称重
这题肯定不是状压DP，而是应用了状压思想的一道模拟（？）。
做题之前进行了bitset大学习。这题不能用整型存状态的最主要原因是位数不够。
首先对于给定的n，数(1<<n)-1的二进制表示有n个1，于是用i枚举状态。如果状态i中1的个数等于n-m，则开始计算：
开一个bitset b，其中若b的第k位为1，则说明数k可以称量出来。0一定能称量出来。
遍历b的每一位，如果第j位为1，则将b整体左移a[j]位，再按位或。这样做的目的是，让先前b中能称量出来的重量全部加上a[j]。
最后用count方法计算b中1的个数，求其最大值。答案记得减1。
code:
#include <bits/stdc++.h>
#define int long long
using namespace std;
int getcnt(int x){int ans=0;while(x){ans++;x-=x&(-x);}return ans;
}
constexpr int N=21;
int n,m,a[N],ans=INT_MIN;
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m;for(int i=0;i<n;i++){cin>>a[i];}for(int i=0;i<(1<<n);i++){if(getcnt(i)==n-m){bitset<2010>b;b[0]=1;for(int j=0;j<n;j++){if(i&(1<<j)){b|=b<<a[j];}}ans=max(ans,(int)b.count());}}cout<<ans-1;return 0;
}
(6) P1879 [USACO06NOV] Corn Fields G
状压DP。和国王题基本一致。
输入小技巧：把每一行压成一个二进制串（类似炮兵题），转移时方便按位与。
用一个数组st存所有合法的状态，即对于每一个1，满足0 1 0的状态。
和国王题一样，定义f[i][j]表示前i行，第i行的状态序号是j的总种植方案。
在打表st的时候，预处理f[1][num]的值，如果st[num]合法，那么它的值是1。
下面开始转移。枚举行数i、状态序号j，如果(st[j]&a[i-1])!=st[j]，即这个状态根据题中贫瘠土地的分布情况，放不了，则继续枚举；否则枚举下一行。
在枚举下一行时，需要是这一行能放下（同上），且这一行与前一行不冲突。
状态转移方程显然是f[i][k]+=f[i-1][j]。记得取模。
答案是f[n][i]的累积。记得取模。
#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int N=13,M=1<<12,mod=1e8;
int m,n,a[N],f[N][M],st[M],num,ans;
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){int x;cin>>x;a[i]=(a[i]<<1)|x;}}for(int i=0;i<(1<<m);i++){if((i&(i<<1))||(i&(i>>1)))continue;st[++num]=i;if((i&a[1])==i){f[1][num]=1;}}for(int i=2;i<=n;i++){for(int j=1;j<=num;j++){if((st[j]&a[i-1])!=st[j])continue;for(int k=1;k<=num;k++){if(((st[k]&a[i])!=st[k])||(st[j]&st[k]))continue;f[i][k]=(f[i][k]+f[i-1][j])%mod;}}}for(int i=1;i<=num;i++){ans=(ans+f[n][i])%mod;}cout<<ans;return 0;
}
(7) P3694 邦邦的大合唱站队
我永远喜欢BanG Dream!
状压DP。挺难。
注意到本题数据范围，最大乐队数仅为20，故考虑压缩乐队状态。
二进制串i中的1，表示那一位代表的乐队已经排完。
定义f[i]表示达到i状态需要出队的最小人数。
考虑枚举状态i中每一个等于1的位j，则i^(1<<(j-1))表示在乐队j没安排好时，i的前驱状态。
显然f[i]=min(前驱状态值+当前乐队人数-之前队伍中当前乐队的人数)
可以用前缀和维护之前队伍中当前乐队人数的总和，用sum[i][j]记录前i个偶像，属于乐队j的人数和。
具体细节见代码。
code:
#include <bits/stdc++.h>
using namespace std;
constexpr int N=21,M=1e5+5;
int n,m,ans,cnt,f[1<<N],num[N],sum[M][N];
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);memset(f,0x3f,sizeof(f));n=read(),m=read();for(int i=1;i<=n;i++){int x;x=read();num[x]++;for(int j=1;j<=m;j++){sum[i][j]=sum[i-1][j];}sum[i][x]++;}f[0]=0;for(int i=0;i<(1<<m);i++){cnt=0;for(int j=1;j<=m;j++){if(i&(1<<(j-1))){cnt+=num[j];}}for(int j=1;j<=m;j++){if(i&(1<<(j-1))){f[i]=min(f[i],f[i^(1<<(j-1))]+num[j]-(sum[cnt][j]-sum[cnt-num[j]][j]));}}}cout<<f[(1<<m)-1];return 0;
}