萌新刚学OI1e-114514s,求调状压dp模板题
查看原帖
萌新刚学OI1e-114514s,求调状压dp模板题
230875
Surge_of_Force楼主2022/1/25 21:16
#include<bits/stdc++.h>
#define ll long long
const int MAX=5e5+10;
using namespace std;
inline int read() {
  int fh = 1, res = 0; char ch = getchar();
  for(; !isdigit(ch); ch = getchar()) if(ch == '-') fh = -1;
  for(; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ '0');
  res = res * fh;
  return res;
}
inline void write(ll x) {
    if(x<0){putchar('-');x=-x;}
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
int dp[10][100][1<<10],s[1<<10],cnt,jl[1<<10];//dp[i][j][k]:前i行摆j个最后一行状态为k 
int main()
{
	int n=read(),k=read();
	int be=(1<<(n-1));
	for(int i=0;i<=be;i++)
	{
		if((i<<1)&i) continue;
		s[++cnt]=i;
		int t=i;
		while(t)
		{
			jl[cnt]+=(t&1);
			t>>=1;
		}
		if(jl[cnt]>k) cnt--;
	}
	for(int i=1;i<=cnt;i++) dp[1][jl[i]][s[i]]=1;
	for(int i=2;i<=n;i++)
		for(int j=1;j<=cnt;j++)//上一行状态
			for(int q=1;q<=cnt;q++)//本行状态
				if(jl[q]+jl[j]<=k)
				{
					if((s[j]<<1)&s[q]) continue;
					if((s[q]<<1)&s[j]) continue;
					if(s[q]&s[j]) continue;
					for(int p=k;p>=jl[q]+jl[j];p--) dp[i][p][q]+=dp[i-1][p-jl[q]][s[j]];
				}
	ll ans=0;
//	for(int i=1;i<=cnt;i++) cout<<s[i]<<" ";
	for(int i=1;i<=n;i++)
//	{
		for(int j=1;j<=cnt;j++)
			ans+=dp[i][k][s[j]];
//			cout<<dp[i][k][s[j]]<<" ";
//		cout<<endl;
//	}
//	cout<<ans;
	return 0;
}
2022/1/25 21:16
加载中...