YBT 5.4 状态压缩动态规划

时间:2022-08-30 04:15:27

#loj 10170. 「一本通 5.4 例 1」骑士

看数据范围n<=10,所以不是搜索就是状压dp,又因为搜索会超时所以用dp

dp[i][k][j]表示现已经放到第i行,前面共有k个,这一行状态为j

so,dp[i][k][j]=dp[i-1][k-num[j]][t]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define low_bit(x) x&-x;
using namespace std;
inline long long read()
{
long long f=,ans=;char c;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}
return ans*f;
}
long long dp[][][];//dp[i][j][k]表示前i行放k个且第i行的状态为j
long long n,k,s[],num[];
long long cont(long long x)
{
long long c=;
while(x!=)
{
x-=low_bit(x);
c++;
}
return c;
}
int main()
{
n=read(),k=read();
long long ans=;
for(long long i=;i<(<<n)-;i++)
{
if((i&(i<<)))continue;
s[++ans]=i;
num[ans]=cont(i);
}
dp[][][]=;
// for(long long i=1;i<=ans;i++) cout<<s[i]<<" ";cout<<endl;
for(long long i=;i<=n;i++)
{
for(long long j=;j<=ans;j++)
{
for(long long kk=;kk<=k;kk++)
{
if(kk>=num[j])
{
for(long long t=;t<=ans;t++)
{
if(s[t]&s[j]) continue;
if(s[t]&(s[j]<<)) continue;
if(s[t]&(s[j]>>)) continue;
dp[i][j][kk]+=dp[i-][t][kk-num[j]];
// cout<<dp[i][j][k]<<endl;
}
}
}
}
}
long long sum=;
for(long long i=;i<=ans;i++) sum+=dp[n][i][k];
cout<<sum;
}

#loj 10171. 「一本通 5.4 例 2」牧场的安排

一道比较普通的状压dp,关键点就是输入时候怎么处理荒草

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define mod 100000000
using namespace std;
inline long long read()
{
long long f=,ans=;char c;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}
return ans*f;
}
long long m,n;
//dp[i][j]表示第i行用第j个状态
//dp[i][j]+=dp[i-1][k]
long long dp[][];
long long ans[];//ans[i]表示第i行有ans[i]个状态
long long s[][];//s[i][j]表示第i行第j个状态
void init(long long h,long long t)
{
// cout<<t<<endl;
for(long long i=;i<=(<<n)-;i++)
{
if((i&(i<<))||(i&(i>>))||(i&t)) continue;
s[h][++ans[h]]=i;
}
return;
}
int main()
{
m=read(),n=read();
for(long long i=;i<=m;i++)
{
long long s=;
for(long long j=;j<=n;j++)
{
long long x=read();
s=(s<<)+-x;
}
init(i,s);
}
for(long long i=;i<=ans[];i++) dp[][i]=;
// for(long long i=1;i<=m;i++)
// {
// cout<<ans[i]<<endl;
// for(long long j=1;j<=ans[i];j++) cout<<s[i][j]<<" ";
// system("pause");
// }
//
for(long long i=;i<=m;i++)
{
for(long long j=;j<=ans[i];j++)
{
for(long long k=;k<=ans[i-];k++)
{
// cout<<i<<" "<<j<<" "<<k<<" "<<s[i][j]<<" "<<s[i-1][k]<<endl;
if(s[i][j]&s[i-][k]) continue;
// if((s[i][j]>>1)&s[i-1][k]) continue;
// if((s[i][j]<<1)&s[i-1][k]) continue;
dp[i][j]+=dp[i-][k]%mod;
}
}
}
long long sum=;
for(long long i=;i<=ans[m];i++) sum+=dp[m][i]%mod,sum%=mod;
cout<<sum%mod;
}

#loj 10172. 「一本通 5.4 练习 1」涂抹果酱

手打三进制运算即可

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define mod 1000000
using namespace std;
inline long long read()
{
long long f=,ans=;char c;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}
return f*ans;
}
long long n,m,k,a[],dg[];
bool check(long long x)
{
memset(dg,,sizeof(dg));
long long ans=;
while(x!=)
{
dg[++ans]=x%;
x/=;
}
for(long long i=m;i>=;i--)
if(dg[i]==dg[i-]) return false;
return true;
}
long long s[],ans;
long long dg1[],dg2[];
void init()
{
ans=;
long long sry=;
for(long long i=;i<=m;i++) sry*=;
for(long long i=;i<=sry-;i++)
if(check(i))
s[++ans]=i;
return;
}
long long dp[][];
bool check2(long long x,long long y)
{
long long ans1=,ans2=;
memset(dg1,,sizeof(dg1));
memset(dg2,,sizeof(dg2));
while(x!=)
{
dg1[++ans1]=x%;
x/=;
}
while(y!=)
{
dg2[++ans2]=y%;
y/=;
}
for(long long i=m;i>=;i--)
if(dg1[i]==dg2[i]) return false;
return true;
}
long long cx(long long x)
{
for(long long i=;i<=ans;i++)
if(s[i]==x) return i;
}
long long book[][];
int main()
{
n=read(),m=read();
k=read();
for(long long i=;i<=m;i++)
{
a[i]=read();
a[i]-=;
}
long long kk=,sum=;
for(long long i=m;i>=;i--)
{
sum+=a[i]*kk;
kk*=;
}
if(check(sum)==false)
{
cout<<;
return ;
}
init();
for(long long i=;i<=ans;i++)
for(long long j=i;j<=ans;j++)
book[i][j]=book[j][i]=check2(s[i],s[j]);
memset(dp,,sizeof(dp));
for(long long i=;i<=ans;i++) dp[][i]=;
for(long long i=;i<=k;i++)
for(long long j=;j<=ans;j++)
for(long long k=;k<=ans;k++)
if(book[j][k])
{
dp[i][j]+=(dp[i-][k])%mod;
dp[i][j]%=mod;
// cout<<"行:"<<i<<" 状态:"<<j<<" dp[i][j]:"<<dp[i][j]<<endl;
}
long long xxxx=cx(sum);
long long p=dp[k][xxxx]%mod;
if(p==)
{
cout<<;
return ;
}
memset(dp,,sizeof(dp));
for(long long i=;i<=ans;i++) dp[n][i]=;
for(long long i=n-;i>=k;i--)
for(long long j=;j<=ans;j++)
for(long long k=;k<=ans;k++)
if(book[j][k])
{
dp[i][j]+=(dp[i+][k])%mod;
dp[i][j]%=mod;
} long long p1=dp[k][xxxx]%mod;
if(p1==)
{
cout<<;
return ;
}
cout<<(p1*p)%mod;
return ;
}

#loj 10173. 「一本通 5.4 练习 2」炮兵阵地

因为联系是由三行,所以dp数组存行数外还要开两位存这一位和上一位的状态

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define lowbit(x) x&-x
using namespace std;
inline int read()
{
int f=,ans=;char c;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}
return ans*f;
}
int cont(int x)
{
int c=;
while(x!=)
{
x-=lowbit(x);
c++;
}
return c;
}
int ans[];
int s[][];
int n,m;
void init(int ha,int t)
{
for(int i=;i<=(<<m)-;i++)
{
if(i&(i<<)) continue;
if(i&(i<<)) continue;
if(i&(i>>)) continue;
if(i&(i>>)) continue;
if(i&t) continue;
s[ha][++ans[ha]]=i;
}
return;
}
int dp[][][];
int main()
{
n=read(),m=read();
for(int i=;i<=n;i++)
{
char str;
int t=;
for(int j=;j<=m;j++)
{
cin>>str;
if(str=='P') t=(t<<);
else if(str=='H') t=(t<<)+;
}
init(i,t);
}
if(n==)
{
cout<<ans[];
return ;
}
for(int i=;i<=ans[];i++)
{
for(int j=;j<=ans[];j++)
{
int s1=s[][i],s2=s[][j];
if(s1&s2) continue;
dp[][i][j]=max(dp[][i][j],cont(s1)+cont(s2));
}
}
for(int i=;i<=n;i++)
{
for(int j=;j<=ans[i];j++)
{
for(int k=;k<=ans[i-];k++)
{
if(s[i][j]&s[i-][k]) continue;
for(int t=;t<=ans[i-];t++)
{
int s1=s[i][j],s2=s[i-][k],s3=s[i-][t];
if(s1&s2) continue;
if(s1&s3) continue;
if(s2&s3) continue;
dp[i%][j][k]=max(dp[i%][j][k],dp[(i-)%][k][t]+cont(s1)); }
}
}
}
int sum=;
for(int i=;i<=ans[n];i++)
for(int j=;j<=ans[n-];j++)
{
if(s[n][i]&s[n-][j]) continue;
sum=max(sum,dp[n%][i][j]);
}
cout<<sum;
}
/*
5 4
PHPP
PPHH
PPPP
PHPP
PHHP
*/

#loj 10174. 「一本通 5.4 练习 3」动物园

这题的关键点就在小朋友只能看到5个数字

所以只需要状压这5个数字就好了

其实不需要断环为链

因为你可以每次先假设一种状态关系到0(其实是n),1,2,3,4

最后只需要输出关于n的这种最大状态

每次看一下需不需要放

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
inline int read()
{
int f=,ans=;char c;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}
return ans*f;
}
int n,c;
int e,f,l;
int g[][],dp[][];
int main()
{
n=read(),c=read();
for(int p=;p<=c;p++)
{
e=read(),f=read(),l=read();
int scared=;
for(int i=;i<=f;i++)
{
int x=read();
x=(x-e+n)%n;
scared|=(<<x);
}
int happy=;
for(int i=;i<=l;i++)
{
int x=read();
x=(x-e+n)%n;
happy|=(<<x);
}
int sry=;
for(int i=;i<=;i++)
{
if((i&happy)||((sry^i)&scared))
{
g[e][i]++;
// cout<<i<<endl;
}
}
}
int ans=;
for(int s=;s<=;s++)
{
for(int j=;j<=;j++) dp[][j]=-(<<-);
dp[][s<<]=dp[][s<<|]=;
for(int i=;i<=n;i++)
for(int ss=;ss<=;ss++)
dp[i][ss]=max(dp[i-][(ss&)<<],dp[i-][(ss&)<<|])+g[i][ss];
ans=max(ans,max(dp[n][s<<|],dp[n][s<<]));
}
cout<<ans;
}