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
补充：软件开发 , C++ ,
