剪了我N久的枝...終於涉險飄過了...2958ms.....
DP....因為馬的范圍只能影響到兩行之內...所以我每兩行兩行處理...先把兩行內放馬的情況打出來....那麼.兩行放馬10個以下互不沖突..有近5000種放法..直接dp..至少5000*5000*10=2.5*10^8..而且判斷當前狀態能否放在已有皇後的情況下..狀態更新時,前後的馬是否會互相攻擊等相當耗時...
所以...然後就是各種剪枝了.....
開始以為這種方法就是狀態壓縮DP...剛才發現我這壓根就沒壓縮狀態..赤裸裸的DP了....狀態壓縮DP效率高很多...
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;
struct node1
{
int h[9][2],num;
}a[5005],p;
int b[70][2505],bnum[70];
int n,m,dp[2][5005][11];
char arc[10][10];
void build_B() // 當前在兩行內放馬的方案能和哪些放皇後的方案共存
{
int i,j,x1,x2;
for (i=0;i<=63;i++) // 兩行內放皇後，不考慮沖突，一共64種情況
{
x1=i/8+1; x2=i%8+1;
for (j=1;j<=p.num;j++)
{
if (p.h[j][0]==1 && x1==p.h[j][1]) goto A;
if (p.h[j][0]==2 && x2==p.h[j][1]) goto A;
}
b[i][++bnum[i]]=m; // ok,掛到後面去....
A: ;
}
return;
}
void dfs(int y,int x) // 搜索出兩行內放10個以下馬互不沖突的所有情況
{
int i,j;
if (p.num==10) return;
for (i=1;i<=p.num;i++)
{
if (abs(p.h[i][0]-y)==1 && abs(p.h[i][1]-x)==2) return;
if (abs(p.h[i][0]-y)==2 && abs(p.h[i][1]-x)==1) return;
}
p.num++;
p.h[p.num][0]=y; p.h[p.num][1]=x;
a[++m]=p;
build_B();
for (j=x+1;j<=8;j++) dfs(y,j);
for (i=y+1;i<=2;i++)
for (j=1;j<=8;j++)
dfs(i,j);
p.num--;
return;
}
void prework()
{
int i,j,p1,p2,k;
memset(bnum,0,sizeof(bnum));
m=0;
p.num=0;
a[++m]=p;
build_B();
for (i=1;i<=2;i++)
for (j=1;j<=8;j++)
dfs(i,j);
return;
}
bool f(int i,int j) // 判斷方案j在上,方案i在下..能否不沖突
{
int p1,p2;
for (p1=1;p1<=a[i].num;p1++)
for (p2=1;p2<=a[j].num;p2++)
{
if (abs(a[i].h[p1][0]-a[j].h[p2][0]-2)==2 && abs(a[i].h[p1][1]-a[j].h[p2][1])==1) return false;
if (abs(a[i].h[p1][0]-a[j].h[p2][0]-2)==1 && abs(a[i].h[p1][1]-a[j].h[p2][1])==2) return false;
}
return true;
}
int getnow(int t) // 將這兩行皇後的情況轉化成相應的代號
{
int x1,x2;
for (x1=1;x1<=8;x1++)
if (arc[t][x1]=='*') break;
for (x2=1;x2<=8;x2++)
if (arc[t+1][x2]=='*') break;
x1--; x2--;
return x1*8+x2;
}
int main()
{
int T,ii,jj,i,j,x,t,k,now,pre,ans,num1,num2;
prework();
scanf("%d",&T);
while (T--)
{
scanf("%d",&n);
for (i=0;i<=8;i++) gets(arc[i]+1);
memset(dp,0,sizeof(dp));
k=0;
now=getnow(1);
num1=bnum[now];
for (ii=1;ii<=num1;ii++)
{
i=b[now][ii];
dp[k][i][a[i].num]=1;
}
pre=now;
for (t=3;t<=8;t+=2)
{
k=1-k;
memset(dp[k],0,sizeof(dp[k]));
now=getnow(t);
num1=bnum[now];
num2=bnum[pre];
for (ii=1;ii<=num1;ii++)
{
i=b[now][ii];
for (jj=1;jj<=num2;jj++)
{
j=b[pre][jj];
if (a[i].num+a[j].num>n || !f(j,i)) continue; // 耗時！！
for (x=n-a[i].num;x>=a[j].num;x--)
dp[k][i][a[i].num+x]+=dp[1-k][j][x];
}
}
pre=now;
}
ans=0;
for (i=1;i<=m;i++) ans+=dp[k][i][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;
struct node1
{
int h[9][2],num;
}a[5005],p;
int b[70][2505],bnum[70];
int n,m,dp[2][5005][11];
char arc[10][10];
void build_B() // 當前在兩行內放馬的方案能和哪些放皇後的方案共存
{
int i,j,x1,x2;
for (i=0;i<=63;i++) // 兩行內放皇後，不考慮沖突，一共64種情況
{
x1=i/8+1; x2=i%8+1;
for (j=1;j<=p.num;j++)
{
if (p.h[j][0]==1 && x1==p.h[j][1]) goto A;
if (p.h[j][0]==2 && x2==p.h[j][1]) goto A;
}
b[i][++bnum[i]]=m; // ok,掛到後面去....
A: ;
}
return;
}
void dfs(int y,int x) // 搜索出兩行內放10個以下馬互不沖突的所有情況
{
int i,j;
if (p.num==10) return;
for (i=1;i<=p.num;i++)
{
if (abs(p.h[i][0]-y)==1 && abs(p.h[i][1]-x)==2) return;
if (abs(p.h[i][0]-y)==2 && abs(p.h[i][1]-x)==1) return;
}
p.num++;
p.h[p.num][0]=y; p.h[p.num][1]=x;
a[++m]=p;
build_B();
for (j=x+1;j<=8;j++) dfs(y,j);
for (i=y+1;i<=2;i++)
for (j=1;j<=8;j++)
dfs(i,j);
p.num--;
return;
}
void prework()
{
int i,j,p1,p2,k;
memset(bnum,0,sizeof(bnum));
m=0;
p.num=0;
a[++m]=p;
build_B();
for (i=1;i<=2;i++)
for (j=1;j<=8;j++)
dfs(i,j);
return;
}
bool f(int i,int j) // 判斷方案j在上,方案i在下..能否不沖突
{
int p1,p2;
for (p1=1;p1<=a[i].num;p1++)
for (p2=1;p2<=a[j].num;p2++)
{
if (abs(a[i].h[p1][0]-a[j].h[p2][0]-2)==2 && abs(a[i].h[p1][1]-a[j].h[p2][1])==1) return false;
if (abs(a[i].h[p1][0]-a[j].h[p2][0]-2)==1 && abs(a[i].h[p1][1]-a[j].h[p2][1])==2) return false;
}
return true;
}
int getnow(int t) // 將這兩行皇後的情況轉化成相應的代號
{
int x1,x2;
for (x1=1;x1<=8;x1++)
if (arc[t][x1]=='*') break;
for (x2=1;x2<=8;x2++)
if (arc[t+1][x2]=='*') break;
x1--; x2--;
return x1*8+x2;
}
int main()
{
int T,ii,jj,i,j,x,t,k,now,pre,ans,num1,num2;
prework();
scanf("%d",&T);
while (T--)
{
scanf("%d",&n);
for (i=0;i<=8;i++) gets(arc[i]+1);
memset(dp,0,sizeof(dp));
k=0;
now=getnow(1);
num1=bnum[now];
for (ii=1;ii<=num1;ii++)
{
i=b[now][ii];
dp[k][i][a[i].num]=1;
}
pre=now;
for (t=3;t<=8;t+=2)
{
k=1-k;
memset(dp[k],0,sizeof(dp[k]));
now=getnow(t);
num1=bnum[now];
num2=bnum[pre];
for (ii=1;ii<=num1;ii++)
{
i=b[now][ii];
for (jj=1;jj<=num2;jj++)
{
j=b[pre][jj];
if (a[i].num+a[j].num>n || !f(j,i)) continue; // 耗時！！
for (x=n-a[i].num;x>=a[j].num;x--)
dp[k][i][a[i].num+x]+=dp[1-k][j][x];
}
}
pre=now;
}
ans=0;
for (i=1;i<=m;i++) ans+=dp[k][i][n];
printf("%d\n",ans);
}
return 0;
}
