HOJ 1472
xnozero吧
全部回复
仅看楼主
level 12
XNoZero 楼主
#include<stdio.h>
#include<string.h>
long long   dp[12][3000];
int sc[200000][2];
int tnum;
int n,k;
void dfs(int w,int start,int end)
{
     if(w>k)
       return;
     if(w==k)
       {
           sc[tnum][0]=start;
           sc[tnum][1]=end;
           tnum++;
           return;
       }
     dfs(w+2,(start<<2)
+3
,(end<<2)+3);
     dfs(w+1,(start<<1)+1,end<<1);
     dfs(w+1,start<<1,(end<<1)+1);
}
main()
{
     int d,p;
     int temp;
     while(scanf("%d %d",&n,&k)==2)
     {
         if(n+k==0)
           break;
         if(n*k%2!=0)
           printf("0\n");
         else
         {
         if(n>k)
          {
              temp=n;
              n=k;
              k=temp;
          }
          tnum=0;
          memset(sc,0,sizeof(sc));
          memset(dp,0,sizeof(dp));
          dfs(0,0,0);
          dp[0][0] = 1;
          for(d=1;d<=n+1;d++)
            for(p=0;p<tnum;p++)
             {
                  dp[d][sc[p][1]]+=dp[d-1][sc[p][0]];
             }
          printf("%lld\n",dp[n+1][( 1 << k ) - 1]);
         }
     }
     return 0;
}
2010年12月12日 16点12分 1
1