2025杭电多校第六场钥匙迷宫取模传送排序cats的max如何实现？
摘要：cats 的 max dp #子集合dp #状态压缩dp #状态压缩 题目 思路 本题只需要考虑(k<m)的情况，因为(kgeq m)时，每一列都必定可以选到其最大值，暴力即可算出答案 考虑到(mleq1
cats 的 max
dp #子集合dp #状态压缩dp #状态压缩
题目
思路
本题只需要考虑\(k<m\)的情况，因为\(k\geq m\)时，每一列都必定可以选到其最大值，暴力即可算出答案
考虑到\(m\leq13\)，所以对每行进行状态压缩
\(mp[N][N]\)用来储存矩阵
\(a[i][mask]\)代表第\(i\)行中，\(mask(2)\)所对应列的元素之和
如\(mask:10010\)，则\(a[i][mask]=mp[i][1]+mp[i][4]\)
\(mask\)中位置\(pos\)为1就代表第\(pos\)列的最大值取在\(mp[ i][pos]\)
如何预处理\(a[i][mask]\)呢？
如果对于每一行\(i\)所储存的\(2^m\)个\(mask\)进行遍历，把1的位置加进\(a[i][mask]\)中，时间复杂度将来到\(o(n·m·2^m)\)，\(TLE\)
因此需要采用前缀优化：通过\(lowbit\)将\(mask\)拆分为\(lowbit\ ,mask\wedge lowbit\)，通过递推\(a[i][mask]=a[i][lowbit]+a[i][mask \wedge lowbit]\)线性预处理出所有情况
\(lowbit\leq mask\ ,mask\wedge lowbit<mask\)，而遍历\(mask\)时是从小到大遍历的，因此该递推即利用了之前处理好的前缀来优化复杂度
\(b[mask]\)代表所有\(a[i][mask]\ i\in[1,n]\)中的最大值
\(dp[cnt][mask]\)代表：现在选择了\(cnt\)行，这\(cnt\)行的状态或运算后为\(mask\)的权值最大值
状态转移：
遍历\(k\)次选择，对于一个\(mask\)，其子集记为\(mask2\)，则二者的补集为\(mask\wedge mask 2\)
\[dp[cnt][mask2]\times b[mask\wedge mask 2]=dp[cnt+1][mask]
\]
当前选了\(cnt\)行，状态为\(mask 2\)，那么其与\(mask\wedge mask 2\)或运算后即可转移到\(mask\)状态，\(b[mask\wedge mask 2]\)就相当于选了新的一行，并且保证新的一行上的列最值与之前状态的列最值不会重叠（补集的作用）
一般dp由后往前写，所以修改一下即可：
\[dp[cnt][mask]=dp[cnt-1][mask2]\times b[mask\wedge mask 2]
\]
枚举所有的\(mask\)及其子集的复杂度为\(3^m\)，所以总复杂度为\(o(m·3^m)\)
最后直接输出\(dp[k][one]\)即可
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<queue>
#include<cmath>
#include<unordered_map>
#include<set>
using namespace std;
using ll = long long;
#define rep(i, a, b) for(ll i = (a); i <= (b); i ++)
#define per(i, a, b) for(ll i = (a); i >= (b); i --)
#define see(stl) for(auto&ele:stl)cout<<ele<<" "; cout<<'\n';
const ll inf = 1e9 + 5;
#define int ll
const int N=1005,M=(1<<14);
int mp[N][N],a[N][M],dp[N][M],b[M];
void see2(int x){
while(x){
cout<<(x&1);
x>>=1;
}
}
void eachT() {
int n,m,k;cin>>n>>m>>k;
int one=(1<<m)-1;
rep(tim,1,k){
rep(mk,0,one)b[mk]=0,dp[tim][mk]=0;
}