• YBTOJ 状压dp合集

    qwq

    种植方案

    对于同一行上的状态可以预处理，只有二进制表示中不存在连续的1的状态才记为合法，这样需要枚举的状态数就只有不到400个了。

    对于相邻两行间的状态判断，设它们分别选择的状态为 s t i st_i sti​ 和 s t j st_j stj​，那么只有 s t i & s t j st_i\&st_j sti​&stj​ 为0的时候才能保证上下不相邻。

    对于不能种草的限制，将每一行的限制状态压缩成 f i f_i fi​，不能种草为1，那么若当前选择的状态为 s t i st_i sti​，且 s t i & f i st_i\&f_i sti​&fi​ 不为0，说明有不能种草的地方种草了，不合法。

    状压完dp就很简单了。

    #include
#define ll long long
#define ff(i,s,e) for(int i=s;i<=(e);++i)
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int N=5000,mod=1e8;
int m,n,a[15][15];
int st[N],tot;
int f[N],dp[15][N];
inline void init(){
	ff(i,0,(1<<n)-1){
		if(((i&(i<<1))==0)&&((i&(i>>1))==0)) st[++tot]=i;
	}
}
signed main(){
	m=read(),n=read();
	ff(i,1,m) ff(j,1,n){
		a[i][j]=read();
		f[i]=(f[i]<<1)+(a[i][j]^1);
	}
	init();
	int ans=0;
	dp[0][1]=1;
	ff(i,1,m){
		ff(j,1,tot){
			if(st[j]&f[i]) continue;
			ff(k,1,tot) if(!(st[k]&st[j])){
				dp[i][j]+=dp[i-1][k];
				if(dp[i][j]>=mod) dp[i][j]-=mod;
			}
		}
	}
	ff(i,1,tot){
		ans+=dp[m][i];
		if(ans>=mod) ans-=mod;
	}
	printf("%d",ans);
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45

    最短路径

    设 f [ i ] [ s t ] f[i][st] f[i][st] 为当前在点 i i i，当前走过的点的二进制状态表示为 s t st st 时的最短路，那么枚举每一个已经被走过的点作为出发点，不断更新最小值即可。

    	ff(st,0,(1<<n)-1){
		ff(i,0,n-1){
			if(!(st&(1<<i))) continue;
			ff(j,0,n-1){
				if(j==i||!(st&(1<<j))) continue;
				f[i][st]=min(f[i][st],f[j][st^(1<<i)]+a[i][j]);
			}
		}
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    涂抹果酱

    三进制状压dp。

    借鉴第一题的思想，先预处理出每一行的合法状态，相邻两行之间的状态是否合法没有位运算不好判断，可以提前预处理一遍，结果拿数组记录，dp的时候直接调用即可。

    从第 k k k 行往上dp一遍，再从第 k k k 行往下dp一遍，最终方案数即填第 1 1 1 行的方案数 × \times × 填第 n n n 行的方案数。

    然后！！！数组空间一定要开够 3 m 3^m 3m！！！习惯了二进制状压直接拿位运算开debug了一个世纪/kk

    #include
#define ll long long
#define ff(i,s,e) for(int i=s;i<=(e);++i)
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int N=1e4+5,M=6,MM=(1<<6),mod=1e6;
int n,m,kk,a,mi[M],pos;
int tot,st[MM];
int f[N][MM];
bool ok[MM][MM];
inline void init(){
	mi[0]=1;
	ff(i,1,m) mi[i]=mi[i-1]*3;
	ff(i,0,mi[m]-1){
		int flag=1;
		ff(j,1,m-1){
			int pre=i/mi[j-1]%3,now=i/mi[j]%3;
			if(pre==now){flag=0;break;}
		}
		if(flag) st[++tot]=i;
		if(i==a) pos=tot;
	}
	ff(i,1,tot) ff(j,i+1,tot){
		int flag=1;
		ff(k,0,m-1){
			int x=st[i]/mi[k]%3,y=st[j]/mi[k]%3;
			if(x==y){flag=0;break;}
		}
		if(flag) ok[i][j]=ok[j][i]=1;
	}
}
signed main(){
	n=read(),m=read(),kk=read();
	int pre=0,x;
	ff(i,1,m){
		x=read();
		if(x==pre) return printf("0"),0;
		a=a*3+x-1,pre=x;
	}
	init();
	f[kk][pos]=1;
	for(int i=kk-1;i;--i) ff(j,1,tot) ff(k,1,tot){
		if(!ok[j][k]) continue;
		f[i][j]+=f[i+1][k];
		if(f[i][j]>=mod) f[i][j]-=mod;
	}
	ff(i,kk+1,n) ff(j,1,tot) ff(k,1,tot){
		if(!ok[j][k]) continue;
		f[i][j]+=f[i-1][k];
		if(f[i][j]>=mod) f[i][j]-=mod;
	}
	int sum1=0,sum2=0;
	ff(i,1,tot){
		sum1+=f[1][i],sum2+=f[n][i];
		if(sum1>=mod) sum1-=mod;
		if(sum2>=mod) sum2-=mod;
	}
	printf("%lld",1ll*sum1*sum2%mod);
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66

    炮兵阵地

    依然预处理每一行的合法状态以及该状态对答案的贡献，dp的时候由于影响第 i i i 行填法的只有第 i i i 行地形，第 i − 1 i-1 i−1 和第 i − 2 i-2 i−2 行，于是可以设 f [ i ] [ j ] [ k ] f[i][j][k] f[i][j][k] 为第 i i i 行状态为 j j j，第 i − 1 i-1 i−1 行状态为 k k k 时最多能放的炮兵数量，暴力枚举第 i i i 行填法，第 i − 1 i-1 i−1 行填法和第 i − 2 i-2 i−2 行填法，暴力dp即可。由于发现每一行的合法状态最多只有60种，所以最高时间复杂度 O ( 6 0 3 × n ) O(60^3 \times n) O(603×n)，可以通过。

    #include
#define ll long long
#define ff(i,s,e) for(int i=s;i<=(e);++i)
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int N=105,M=15,MM=(1<<10)+5;
int n,m,a[N];
char s[M];
int st[MM],val[MM],tot;
int f[N][MM][MM];
inline void init(){
	ff(i,0,(1<<m)-1){
		if((i&(i<<1))||(i&(i<<2))||(i&(i>>1))||(i&(i>>2))) continue;
		st[++tot]=i;
		ff(j,0,m-1) if(i&(1<<j)) ++val[tot];
	}
}
signed main(){
	n=read(),m=read();
	ff(i,1,n){
		scanf("%s",s+1);
		ff(j,1,m){
			int now=(s[j]=='H')?1:0;
			a[i]=(a[i]<<1)+now;
		}
	}
	init();
	ff(i,1,tot) f[1][i][1]=val[i];
	ff(x,2,n) ff(i,1,tot){
		if(st[i]&a[x]) continue;
		ff(j,1,tot){
			if((st[i]&st[j])||(st[j]&a[x-1])) continue;
			ff(k,1,tot){
				if((st[i]&st[k])||(st[j]&st[k])||(st[k]&a[x-2])) continue;
				f[x][i][j]=max(f[x][i][j],f[x-1][j][k]+val[i]);
			}
		}
	}
	int ans=0;
	ff(i,1,tot) ff(j,1,tot) ans=max(ans,f[n][i][j]);
	printf("%d",ans);
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49

    最优组队

    暴力做法：设 f [ i ] f[i] f[i] 为状态为 i i i 时的最大答案，枚举每一个状态 i i i，再枚举每一个状态 j j j，若 j j j 是 i i i 的子集，则更新 f [ i ] = max ⁡ ( f [ i ] , f [ j ] + f [ i f[i]=\max(f[i],f[j]+f[i f[i]=max(f[i],f[j]+f[i x o r xor xor j ] ) j]) j])，时间复杂度 O ( 4 n ) O(4^n) O(4n)。

    好巧妙的优化：

    f o r ( i n t for(int for(int j = ( i − 1 ) & i ; j ; j = ( j − 1 ) & i ) j=(i-1)\&i;j;j=(j-1)\&i) j=(i−1)&i;j;j=(j−1)&i)

    这样一个循环实现的功能是从大到小枚举 i i i 的每一个子集。

    证明：按位与运算得到的数不可能变大，所以易证从大到小，即一定不会重复枚举。为什么是每一个呢？设二进制最末位的 1 1 1 后面有 x x x 个 0 0 0，减一之后 1 1 1 变成 0 0 0，而它后面的 x x x 个 0 0 0 全部变成 1 1 1，再按位与一下得到的后 x x x 位数就与原来 i i i 的后 x x x 位数相同，这之间一定没有 i i i 的子集了，所以每一个子集都不会被漏掉（我这什么语文水平啊qwq

    由于有 n n n 位，其中有 x x x 个 1 1 1 的二进制数有 C n x C_n^x Cnx​ 个，每个 1 1 1 都有选和不选两种情况，所以每个二进制数的子集数为 2 k 2^k 2k，则时间复杂度为 ∑ i = 1 n C n i × 2 i = ∑ i = 1 n C n i × 2 i × 1 n − k = ( 2 + 1 ) n = 3 n \sum_{i=1}^n C_n^i \times 2^i = \sum_{i=1}^n C_n^i \times 2^i \times 1^{n-k} = (2+1)^n=3^n ∑i=1n​Cni​×2i=∑i=1n​Cni​×2i×1n−k=(2+1)n=3n，最后一步的依据是神神奇奇的二项式定理。

    最短路径

    当年一刷ybt的时候跑分层图永远30分的题qwq

    这次再看思路很清楚：将 s s s 和 t t t 加入标记点集合，以每个标记点为起点分别跑一次dij，记录标记点两两之间的距离，若此时发现 s s s 和 t t t 不连通直接输出 − 1 -1 −1。

    然后就是朴素的状压dp了，设 f [ i ] [ j ] f[i][j] f[i][j] 为当前在第 i i i 个关键点，经过关键点状态为 j j j 的最短路，枚举上一次在哪个关键点，转移一下即可。初始化除起点外距离均为正无穷，最后若发现答案为正无穷则输出 − 1 -1 −1。

    时间复杂度 O ( ( k + 2 ) × m l o g m + ( k + 2 ) 2 × 2 k + 2 ) O((k+2) \times mlogm+(k+2)^2 \times 2^{k+2}) O((k+2)×mlogm+(k+2)2×2k+2)，期望得分100。然而没判 − 1 -1 −1 挂十分，没开long long挂十分，警钟长鸣。

    #include
#define int long long
#define ff(i,s,e) for(int i=s;i<=(e);++i)
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int N=5e4+5,M=1e5+5,K=15,KK=(1<<12)+5;
int n,m,k,s,t,a[N];
int head[N],cnt;
struct qwq{
	int v,w,nxt;
}e[M];
inline void add(int u,int v,int w){
	e[++cnt]=qwq{v,w,head[u]},head[u]=cnt;
}
int d[K][K];
typedef pair<int,int> pir;
priority_queue<pir,vector<pir>,greater<pir> > q;
int dis[N];
inline void dij(int s){
	memset(dis,0x7f,sizeof(dis));
	dis[s]=0,q.push(make_pair(0,s));
	while(!q.empty()){
		int x=q.top().second;
		q.pop();
		for(int i=head[x];i;i=e[i].nxt){
			int v=e[i].v,w=e[i].w;
			if(dis[v]>dis[x]+w) dis[v]=dis[x]+w,q.push(make_pair(dis[v],v));
		}
	}
}
int f[K][KK];
signed main(){
	n=read(),m=read(),k=read(),s=read(),t=read();
	ff(i,1,m){
		int u=read(),v=read(),w=read();
		add(u,v,w);
	}
	a[1]=s,++k;
	ff(i,2,k) a[i]=read();
	a[++k]=t;
	ff(i,1,k){
		dij(a[i]);
		ff(j,1,k) d[i][j]=dis[a[j]];
	}
	if(d[1][k]==0x7f) return printf("-1"),0;
	memset(f,0x7f,sizeof(f));
	int inf=f[1][1];
	f[1][1]=0;
	ff(st,2,(1<<k)-1){
		ff(i,1,k){
			if(!(st&(1<<i-1))) continue;
			ff(j,1,k){
				if(j==i||!(st&(1<<j-1))) continue;
				f[i][st]=min(f[i][st],f[j][st^(1<<i-1)]+d[j][i]); 
			}
		}
	}
	if(f[k][(1<<k)-1]==inf) printf("-1");
	else printf("%lld",f[k][(1<<k)-1]);
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67

    小绿小蓝

    每一个状态遇到的怪兽的数量是一定的，所以只需要dp求每一个状态所走路径长度的最大值即可。

    注意要当当前状态合法且经过 t t t 时才更新答案。

    由于有重边，所以如果邻接矩阵存图要取重边中边长最大的。

    #include
#define ll long long
#define ff(i,s,e) for(int i=s;i<=(e);++i)
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int N=19,M=515,NN=(1<<17)+5;
int n,m,a[N],s,t;
int e[N][N];
int f[N][NN]; 
signed main(){
	n=read(),m=read();
	ff(i,1,n) a[i]=read();
	ff(i,1,m){
		int u=read(),v=read(),w=read();
		e[u][v]=max(e[u][v],w);
	}
	s=read(),t=read();
	memset(f,-0x3f3f3f3f,sizeof(f));
	f[s][1<<s-1]=0;
	double ans=1e9;
	ff(st,1,(1<<n)-1) ff(i,1,n){
		if(!(st&(1<<i-1))) continue;
		ff(j,1,n){
			if(e[j][i]==0||(st&(1<<j-1))==0||i==j) continue;
			f[i][st]=max(f[i][st],f[j][st^(1<<i-1)]+e[j][i]);
		}
		if((st&(1<<t-1)==0)||f[t][st]<0) continue;
		int sum=0;
		ff(i,1,n) if(st&(1<<i-1)) sum+=a[i];
		ans=min(ans,1.0*sum/f[t][st]);
	} 
	printf("%.3lf",ans);
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40

    擦除序列

    好水的一道题

    考虑预处理记录每一个能构成回文串的状态，dp时枚举每一个状态，再枚举当前这一步消去哪个回文串即可。

    #include
#define ll long long
#define ff(i,s,e) for(int i=s;i<=(e);++i)
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int N=18,NN=(1<<16)+5;
int n,st[NN],tot;
char s[N],qwq[N]; 
inline bool pd(int len){
	for(int i=1,j=len;i<=j;++i,--j) if(qwq[i]!=qwq[j]) return 0;
	return 1; 
}
inline void init(){
	ff(i,1,(1<<n)-1){
		int len=0;
		ff(j,1,n) if(i&(1<<j-1)) qwq[++len]=s[j];
		if(pd(len)) st[++tot]=i;
	}
}
int f[NN];
signed main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	init();
	memset(f,0x3f3f3f3f,sizeof(f));
	f[0]=0;
	ff(i,1,(1<<n)-1) ff(j,1,tot){
		if((st[j]|i)!=i) continue;
		f[i]=min(f[i],f[i^st[j]]+1);
	}
	printf("%d",f[(1<<n)-1]);
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39

    图的计数

    设 f [ i ] [ j ] f[i][j] f[i][j] 为从第一层到第 i i i 层，到第 i i i 层的 k k k 个点的路径条数的奇偶状态为 j j j 的方案数，那么只需要分取反和不取反两种情况进行dp转移即可。

    #include
#define ll long long
#define ff(i,s,e) for(int i=s;i<=(e);++i)
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int mod=998244353,K=12,KK=1030,M=1e4+5;
int m,kk,a[M][M],b[M][M];
ll f[M][KK];
signed main(){
	m=read(),kk=read();
	ff(i,0,kk-1) a[1][0]|=(read()<<i);
	ff(i,2,m-2) ff(j,0,kk-1) ff(k,0,kk-1){
		int x=read();
		a[i][j]|=(x<<k),b[i][k]|=(x<<j);
	}
	ff(i,0,kk-1) a[m][0]|=(read()<<i);
	f[2][a[1][0]]=1;
	ff(i,2,m-2) ff(st,0,(1<<kk)-1){
		int s1=0,s2=0;
		ff(j,0,kk-1) if(st&(1<<j)) s1^=a[i][j],s2^=b[i][j];
		f[i+1][s1]+=f[i][st],f[i+1][s2]+=f[i][st];
		if(f[i+1][s1]>=mod) f[i+1][s1]-=mod;
		if(f[i+1][s2]>=mod) f[i+1][s2]-=mod;
	}
	ll ans=0;
	ff(st,0,(1<<kk)-1){
		int tot=0;
		ff(i,0,kk-1) if((a[m][0]&(1<<i))&&(st&(1<<i))) tot^=1;
		if(!tot){
			ans+=f[m-1][st];
			if(ans>=mod) ans-=mod;
		}
	}
	printf("%lld",ans);
	return 0;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
  • 相关阅读:
    ubuntu 安装jdk8
    Leetcode第 368 场周赛
    如何找到合适代理类型？为您多角度剖析!
    SimpleServletHandlerAdapter类简介说明
    Open3D 二维凸包计算
    第十三届蓝桥杯国赛真题 PythonB组 复盘以及获奖感言（国一！！！）
    求实数的整数次幂(循环版)(高效)（位运算解题）
    MyCat-web安装文档：安装Zookeeper、安装Mycat-web
    深度学习的基本原理和算法
    华为机试真题 Java 实现【无向图染色】【2022.11 Q4新题】
  • 原文地址：https://blog.csdn.net/zcxxn/article/details/126481418