Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  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(){
    //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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator