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