| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
记忆优化下就好了#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(){
//freopen("read.txt", "r", stdin);
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: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator