| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
发个代码,DFS+状压DP,16ms,26行(应该还可以压短)#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator