HDOJ 4529 - N騎士問題 狀態壓縮DP

  狀態壓縮DP果然比自己摸索出來的DP效率高多了...406ms..輕松飄過~~

Program:

[cpp]
#include<iostream>  
#include<cmath>  
#include<stack>  
#include<queue>  
#include<set>  
#include<algorithm>  
#include<stdio.h>  
#include<string.h>  
#define ll long long  
#define oo 1000000007  
using namespace std; 
char arc[10][10]; 
int cnt[260],dp[10][260][260][12]; 
bool f[3][260][260]; 
bool ok1(int t,int y,int x) 
{ 
       int i,j,a[10],anum,b[10],bnum; 
       anum=0; 
       for (i=8;i>=1;i--) 
       { 
              if (y%2) a[++anum]=i; 
              y/=2; 
       } 
       bnum=0; 
       for (i=8;i>=1;i--) 
       { 
              if (x%2) b[++bnum]=i; 
              x/=2; 
       } 
       for (i=1;i<=anum;i++) 
         for (j=1;j<=bnum;j++) 
         { 
              if (t==1 && abs(a[i]-b[j])==2) return false; 
              if (t==2 && abs(a[i]-b[j])==1) return false; 
         } 
       return true; 
} 
int getcnt(int n) 
{ 
       int m=0; 
       while (n) 
       { 
             n=n&(n-1); 
             m++; 
       } 
       return m; 
} 
bool ok2(int t,int x) 
{ 
       int i;  
       for (i=8;i>=1 && x;i--) 
       { 
              if (x%2 && arc[t][i]=='*') return false; 
              x/=2; 
       } 
       return true; 
} 
int main() 
{        
       int T,n,t,i,j,x,k,ans; 
       memset(f,false,sizeof(f)); 
       for (n=1;n<=2;n++) 
         for (i=0;i<256;i++) 
           for (j=0;j<256;j++) 
             if (ok1(n,i,j)) f[n][i][j]=true; 
       for (i=0;i<256;i++) cnt[i]=getcnt(i); 
       scanf("%d",&T); 
       while (T--) 
       {   
              scanf("%d",&n); 
              for (i=0;i<=8;i++) gets(arc[i]+1);  
              memset(dp,0,sizeof(dp)); 
              for (i=0;i<256;i++) 
                if (cnt[i]<=n && ok2(1,i)) dp[1][0][i][cnt[i]]=1; 
              for (t=2;t<=8;t++) 
                for (i=0;i<256;i++) 
                  if (ok2(t,i)) 
                    for (j=0;j<256;j++) 
                      if (f[1][j][i]) 
                        for (x=0;x<256;x++) 
                           if (f[2][x][i]) 
                             for (k=cnt[x]+cnt[j];k<=n-cnt[i];k++) 
                               dp[t][j][i][k+cnt[i]]+=dp[t-1][x][j][k]; 
              ans=0; 
              for (i=0;i<256;i++) 
                for (j=0;j<256;j++)  
                     ans+=dp[8][i][j][n]; 
              printf("%d\n",ans); 
               
       }  
       return 0; 
} 

#include<iostream>
#include<cmath>
#include<stack>
#include<queue>
#include<set>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#define ll long long
#define oo 1000000007
using namespace std;
char arc[10][10];
int cnt[260],dp[10][260][260][12];
bool f[3][260][260];
bool ok1(int t,int y,int x)
{
       int i,j,a[10],anum,b[10],bnum;
       anum=0;
       for (i=8;i>=1;i--)
       {
              if (y%2) a[++anum]=i;
              y/=2;
       }
       bnum=0;
       for (i=8;i>=1;i--)
       {
              if (x%2) b[++bnum]=i;
              x/=2;
       }
       for (i=1;i<=anum;i++)
         for (j=1;j<=bnum;j++)
         {
              if (t==1 && abs(a[i]-b[j])==2) return false;
              if (t==2 && abs(a[i]-b[j])==1) return false;
         }
       return true;
}
int getcnt(int n)
{
       int m=0;
       while (n)
       {
             n=n&(n-1);
             m++;
       }
       return m;
}
bool ok2(int t,int x)
{
       int i;
       for (i=8;i>=1 && x;i--)
       {
              if (x%2 && arc[t][i]=='*') return false;
              x/=2;
       }
       return true;
}
int main()
{      
       int T,n,t,i,j,x,k,ans;
       memset(f,false,sizeof(f));
       for (n=1;n<=2;n++)
         for (i=0;i<256;i++)
           for (j=0;j<256;j++)
             if (ok1(n,i,j)) f[n][i][j]=true;
       for (i=0;i<256;i++) cnt[i]=getcnt(i);
       scanf("%d",&T);
       while (T--)
       { 
              scanf("%d",&n);
              for (i=0;i<=8;i++) gets(arc[i]+1);
              memset(dp,0,sizeof(dp));
              for (i=0;i<256;i++)
                if (cnt[i]<=n && ok2(1,i)) dp[1][0][i][cnt[i]]=1;
              for (t=2;t<=8;t++)
                for (i=0;i<256;i++)
                  if (ok2(t,i))
                    for (j=0;j<256;j++)
                      if (f[1][j][i])
                        for (x=0;x<256;x++)
                           if (f[2][x][i])
                             for (k=cnt[x]+cnt[j];k<=n-cnt[i];k++)
                               dp[t][j][i][k+cnt[i]]+=dp[t-1][x][j][k];
              ans=0;
              for (i=0;i<256;i++)
                for (j=0;j<256;j++)
                     ans+=dp[8][i][j][n];
              printf("%d\n",ans);
             
       }
       return 0;
}