Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 记忆优化下就好了

Posted by lmc596922196 at 2015-08-22 16:19:42 on Problem 1143
```#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
#define B(x) (1<<(x))
const int INF = 0x3f3f3f3f;
int a[22], n, ans[22], cnt;
int state[22][22], mutil[22], vis[22];
int B[22], dp[B(19) + 5];

void Init(){
for(int i = 2; i <= 20; i++){
B[i] = B(i - 2);
}
for(int i = 2; i <= 20; i++){
for(int j = i + 1; j <= 20; j++){
for(int k1 = 1; k1 <= 20; k1++){
for(int k2 = 1; k2 <= 20; k2++){
if(k1 * i + k2 * j <= 20){
state[i][j] |= B[k1 * i + k2 * j];
}
}
}
state[j][i] = state[i][j];
}
}
for(int i = 2; i <= 20; i++){
for(int j = i; j <= 20; j += i)
mutil[i] |= B[j];
}
}

bool dfs(int s){
if(dp[s] != -1) return dp[s];
for(int i = 1; i <= n; i++){
if(s & B[a[i]]) continue;
int st = s;
for(int j = 2; j <= 20; j++){
if(s & B[j])
st |= state[a[i]][j];
}
st |= mutil[a[i]];
if( !dfs(st) ){
dp[s] = 1;
return true;
}
}
dp[s] = 0;
return false;
}

void BY(){
cnt = 0;
int s = 0;
for(int i = 2; i <= 20; i++){
if(!vis[i]) continue;
s |= B[i];
}
memset(dp, -1, sizeof dp);
for(int i = 1; i <= n; i++){
int st = s;
for(int j = 2; j <= 20; j++){
if(s & B[j])
st |= state[a[i]][j];
}
st |= mutil[a[i]];
if(!dfs(st)) ans[cnt++] = a[i];
}
}

int main(){
Init();
int cas = 1;
while(scanf("%d", &n) != EOF){
if(!n) break;
for(int i = 1; i <= 20; i++){
vis[i] = 1;
}
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
vis[a[i]] = 0;
}
BY();
printf("Test Case #%d\n", cas++);
if(!cnt) puts("There's no winning move.");
else{
printf("The winning moves are:");
for(int i = 0; i < cnt; i++)
printf(" %d", ans[i]);
puts("");
}
puts("");
}
return 0;
}
/*
19 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
*/

```

Followed by: