4
30
2016
1

专题:状态压缩动态规划

再不切题就要退役辣,学习老板娘板切专题。

BZOJ 1087 1076 2064 1725 1231 1688 1072 1097 2734 1226 2595 2073 2004 2669
CODEVS 1050 2800 1358 1480 2009 2017 2125 2743 2818 2889 2941 3122 3196  
hdu 3001 3681 4114 4892 4284 1074 3182 4568 4336 1565 2167 4539    

BZOJ:

1087:在N*N的棋盘上放K个互不攻击的王的方案数。

正确姿势:打表233

f[i][j][S]表示第i行状态为S时还剩下j个王可放。位运算预处理一下转移什么的轻易AC了。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define maxn 10
#define maxk 82
#define maxS 512
using namespace std;
int n,k,S;
long long f[maxn][maxk][maxS],cnt[maxS],ans;
int main()
{
	scanf("%d%d",&n,&k);S=1<<n;
	for(int i=0;i<S;i++)if(!(i&(i<<1)))
		for(int x=i;x;x>>=1)cnt[i]+=(x&1);	
	f[0][k][0]=1;
	for(int i=1;i<=n;i++)
		for(int x=1;x<=k;x++)
			for(int s=0;s<S;s++)
				for(int t=0;t<S;t++)
					if(!(s&t)&&!(s&(s<<1))&&!(t&(t<<1))&&!(s&(t<<1))&&!(t&(s<<1))&&cnt[t]<=x)
						f[i][x-cnt[t]][t]+=f[i-1][x][s];	
	for(int i=1;i<=n;i++)
		for(int s=0;s<S;s++)
			ans+=f[i][0][s];
	printf("%lld",ans);
}

1725:

棋盘的给定位置上放置不相邻旗子的方案数。

比上一题还要斯波,f[i][S]表示第i行状态为j的方案数。

#include<cstdio>
#include<cstring> 
#define MO 100000000
using namespace std;
int n,m,s[13],f[13][4096],x,ans;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)scanf("%d",&x),s[i]=(s[i]<<1)+x;
	int S=1<<m;
	for(int i=0;i<S;i++)if(!(i&(i<<1))&&(i|s[1])==s[1])
		f[1][i]=1;
	for(int i=2;i<=n;i++)
		for (int l=0;l<S;l++)if(f[i-1][l])
			for(int r=0;r<S;r++)
				if(!(l&r)&&!(r&(r<<1))&&(r|s[i])==s[i])
					f[i][r]=(f[i][r]+f[i-1][l])%MO;
	for(int i=0;i<S;i++)
		ans=(ans+f[n][i])%MO;
	printf("%d",ans);
}

CODEVS:

1050:轮廓线状压DP,详见http://scarlet.is-programmer.com/posts/181697.html

hdu:

3001:

每个点经过不超过两次的TSP。f[i][S]表示经过点的状态S时,最后一个点为i的最小费用。这里S三进制状压,表示每个点已经遍历的次数。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 11
#define maxS 59049
#define AE(u,v,w) E[Si]=(Ed){v,w},nxt[Si]=idx[u],idx[u]=Si++
#define mi(a,b) a=min(a,b)
using namespace std;
struct Ed{int v,w;}E[maxS];
int f[maxn][maxS],n,m,idx[maxn],nxt[maxS],trn[maxn],Si,u,v,w,S,tri[maxS][maxn],c[maxS];
int main()
{
	trn[0]=1;for(int i=1;i<=10;i++)trn[i]=trn[i-1]*3;
	for(int i=0;i<maxS;i++)for(int j=0,x=i;j<=10;j++,x/=3)tri[i][j]=x%3,c[i]+=((x%3)!=0);
	while(scanf("%d%d",&n,&m)==2)
	{
		Si=0;S=trn[n];
		memset(idx,-1,sizeof(idx));
		memset(f,0x7f7f7f7f,sizeof(f));
		int ans=f[0][0],INF=f[0][0];
		for(int i=1;i<=m;i++)scanf("%d%d%d",&u,&v,&w),u--,v--,AE(u,v,w),AE(v,u,w);
		for(int i=0;i<n;i++)f[i][trn[i]]=0;
		for(int s=0;s<S;s++)
			for(int u=0;u<n;u++)if(tri[s][u]!=0) 
				for(int i=idx[u];i+1;i=nxt[i])if(tri[s][E[i].v]<2)
					mi(f[E[i].v][s+trn[E[i].v]],f[u][s]+E[i].w);
		for(int s=0;s<S;s++)if(c[s]==n)
			for(int i=0;i<n;i++)
				ans=min(ans,f[i][s]);
		if(ans!=INF)printf("%d\n",ans);
		else puts("-1");
	}
}
Category: 罗干 | Tags: 动态规划

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com