Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

发个代码,DFS+状压DP,16ms,26行(应该还可以压短)

Posted by hy8693285 at 2011-07-16 16:23:58 on Problem 2411
#include <stdio.h>
#include <string.h>
int n,m;__int64 dp[12][2049],tmp;
void dfs(int p,int s,int pos)
{
	if(pos==m){dp[p][s]+=tmp;return;}
	dfs(p,s,pos+1);
	if((pos<=m-2)&&!(s&(1<<pos))&&!(s&1<<pos+1)) dfs(p,s|(1<<pos)|(1<<pos+1),pos+2);
}
int main()
{
	scanf("%d%d",&n,&m);
	while((n!=0)&&(m!=0)){
		if(n<m){n=n^m;m=n^m;n=n^m;}
		memset(dp,0,sizeof(dp));
		tmp=1;
		dfs(1,0,0);
		for(int i=2;i<=n;i++) for(int j=0;j<(1<<m);j++){
				if(dp[i-1][j]) tmp=dp[i-1][j];else continue;
				dfs(i,(~j)&((1<<m)-1),0);
			}
		printf("%lld\n",dp[n][(1<<m)-1]);
		scanf("%d%d",&n,&m);
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator