题目链接：

http://acm.hust.edu.cn/vjudge/problem/96343

I Want That Cake

Time Limit: 3000MS
64bit IO Format: %lld & %llu

题意

有m块饼，有两个队各n个人站成一排，现在从第一个人开始吃饼，每个人至少吃一个最多吃k个，最后吃到饼的人所在的队伍胜，现在双方都采取最优策略，问哪个队能胜。

题解

如果两个队站队的形式是ABABAB，那么这就是个明显的博弈论了，然后并不一定是这样站的，不过没关系，我们可以把相邻的相同队伍的看成一个人，那么久变成ABABA的形式了，虽然这样处理之后每个‘人’能吃的饼的限制不同了，但是我们可以直接干一发dfs（记忆化）,根据必胜态推出所有的状态。

注：必胜态：存在一个后继为必败态；必败态：所有的后继都为必胜态

代码

#include<map>

#include<set>

#include<cmath>

#include<queue>

#include<stack>

#include<ctime>

#include<vector>

#include<cstdio>

#include<string>

#include<bitset>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<functional>

using namespace std;

#define X first

#define Y second

#define mkp make_pair

#define lson (o<<1)

#define rson ((o<<1)|1)

#define mid (l+(r-l)/2)

#define sz() size()

#define pb(v) push_back(v)

#define all(o) (o).begin(),(o).end()

#define clr(a,v) memset(a,v,sizeof(a))

#define bug(a) cout<<#a<<" = "<<a<<endl

#define rep(i,a,b) for(int i=a;i<(b);i++)

#define scf scanf

#define prf printf

typedef long long LL;

typedef vector<int> VI;

typedef pair<int,int> PII;

typedef vector<pair<int,int> > VPII;

const int INF=0x3f3f3f3f;

const LL INFL=0x3f3f3f3f3f3f3f3fLL;

const double eps=1e-8;

const double PI = acos(-1.0);

//start----------------------------------------------------------------------

const int maxn=2222;

int n,m,k;

int dp[maxn][maxn];

char str[maxn];

VI lis;

int dfs(int cur,int lef){

    if(dp[cur][lef]!=-1) return dp[cur][lef];

    int& ret=dp[cur][lef];

    if(lef<=lis[cur]*k) return ret=1;

    ret=0;

    for(int i=lis[cur];i<=lis[cur]*k;i++){

        if(dfs(cur+1,lef-i)==0) return ret=1;

    }

    return ret;

}

void init(){

    clr(dp,-1);

    lis.clear();

}

int main() {

    int tc,kase=0;

    scf("%d",&tc);

    while(tc--){

        init();

        scf("%d%d%d",&n,&m,&k);

        scf("%s",str); int len=strlen(str);

        for(int i=0;i<len;i++){

            int j=i;

            while(j<len&&str[i]==str[j]) j++; j--;

            lis.pb(j-i+1);

            i=j;

        }

        int ans=dfs(0,m);

        prf("Case #%d: ", ++kase);

        if(ans){

            if(str[0]=='A') puts("A");

            else puts("B");

        }else{

            if(str[0]=='A') puts("B");

            else puts("A");

        }

    }

    return 0;

}

//end-----------------------------------------------------------------------

巴特西

UVALive 6913 I Want That Cake 博弈+dp

题目链接：

I Want That Cake

题意

题解

代码

最新文章

热门文章