競程作業，2017 交大年度賽 Problem K：FOJ-195
DP 題，他要問說如果有障礙物的話，在 N x N 的棋盤上擺 N 個城堡有幾種擺法
這題我跟本就想不到 QQ
後來是某土木系游泳的時候想到解法告訴我的
就是要一層一層 D 上去，然後我就忘了
以後想到再補
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| #include<iostream>
#include<string.h>
#include<math.h>
#include<bitset>
#define ll unsigned long long int
using namespace std;
bool M[22][22] = {};
ll ji[1048579] = {};
bool isji[1048579] = {};
int n, m;
int BitCount(ll u){
ll uCount;
uCount = u - ((u >> 1) & 033333333333) - ((u >> 2) & 011111111111);
return ((uCount + (uCount >> 3)) & 030707070707) % 63;
}
ll dp(ll state){
if(isji[state]){
return ji[state];
}
ll temp = state;
ll tmp = state;
int wei = 1, ge;
while(tmp = tmp>>1){
wei++;
}
ge = BitCount(state);
if(ge==1&&!M[wei][1]){
isji[state] = 1;
return ji[state] = 1;
}
for(int i=0; i<wei; i++){
if(temp%2&&!M[i+1][ge]){
ji[state] += dp(state-(1<<i));;
}
temp = temp >> 1;
}
isji[state] = 1;
return ji[state];
}
int main(){
int t;
cin>>t;
while(t--){
int x, y;
cin>>n>>m;
memset(M, 0, sizeof(M));
memset(ji, 0, sizeof(ji));
memset(isji, 0, sizeof(isji));
for(int i=0; i<m; i++){
cin>>x>>y;
M[x][y] = 1;
}
ll ans = dp((1 << n)-1);
cout<<ans<<"\n";
}
}
|