Good Luck in CET-4 Everybody!

1
3

Kiki
Cici

1、用博弈论sg函数可以解

根据NP图的关系，发现 n%3=0时，Cici赢，否则Kiki赢

2、用DP去解，用dp[n][f] 表示还剩n张牌时，f先走，谁赢。

1、sg找规律

#include <iostream>
#include <cstdio>
using namespace std;

int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        if(n%3==0) printf("Cici\n");
        else printf("Kiki\n");
    }
    return 0;
}

2、DP方法

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int maxn=1100;
int dp[maxn][2];

int DP(int n,int f){
    if(n<=0) return 1-f;
    if(dp[n][f]!=-1) return dp[n][f];
    if(f==0){
        int ans=1;
        for(int i=1; i<=n ;i=(i<<1) ){
            if(DP(n-i,1-f)<ans ) ans=DP(n-i,1-f);
        }
        return dp[n][f]=ans;
    }else{
        int ans=0;
        for(int i=1; i<=n ;i=(i<<1) ){
            if(DP(n-i,1-f)>ans ) ans=DP(n-i,1-f);
        }
        return dp[n][f]=ans;
    }
}

int main(){
    memset(dp,-1,sizeof(dp));
    int n;
    while(scanf("%d",&n)!=EOF){
        if(DP(n,0)==0) printf("Kiki\n");
        else printf("Cici\n");
    }
    return 0;
}

HDU 1847 Good Luck in CET-4 Everybody! （博弈论sg）,布布扣,bubuko.com

HDU 1847 Good Luck in CET-4 Everybody! （博弈论sg）

原文：http://blog.csdn.net/a1061747415/article/details/36905185