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