Flandre Scarlet's Blog

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

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");
	}
}