<span>uvalive6913 I Want That Cake（博弈dp）</span>
引自：http://www.cnblogs.com/qscqesze/p/5734143.html
题意：
有两支队，每只队都有n个人，一共有m个蛋糕，每个人至少吃一个，最多吃k个。
都采取最优策略，谁吃到最后一个蛋糕，那么那只队就胜利。
按照给定的顺序去吃蛋糕，问你最后谁胜利。
思路：
先缩点，把相同的点都缩成一个点。
那么就变成了ABABABA这样交替的形式了，然后跑DP就好了。
dp[i][j]代表第i层代表的队伍蛋糕还剩j个时的状态
0为必败态，1为必胜态
首先，能把蛋糕吃完的状态为必胜态
然后，能到达必败态的状态为必胜态
只能到达必胜态的状态为必败态
递归回0，m的状态，如果为必胜态则输出第一个吃蛋糕的队伍
否则输出第二个吃蛋糕的队伍
/* *********************************************** Author :devil ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <stack> #include <map> #include <string> #include <cmath> #include <stdlib.h> #define LL long long #define rep(i,a,b) for(int i=a;i<=b;i++) #define dep(i,a,b) for(int i=a;i>=b;i--) #define ou(a) printf("%d\n",a) #define pb push_back #define mkp make_pair template<class T>inline void rd(T &x) { char c=getchar(); x=0; while(!isdigit(c))c=getchar(); while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); } } #define IN freopen("in.txt","r",stdin); #define OUT freopen("out.txt","w",stdout); using namespace std; const int inf=0x3f3f3f3f; const int mod=1e9+7; const int N=2e3+10; char s[N]; int dp[N][N],t,n,m,k,cas; vector<int>eg; bool dfs(int x,int y) { if(y<=0) return 0; if(x==eg.size()) return 1; if(dp[x][y]!=-1) return dp[x][y]; int &ans=dp[x][y]; ans=0; for(int i=eg[x]*k;i>=eg[x];i--) if(!dfs(x+1,y-i)) return ans=1; return ans; } int main() { #ifndef ONLINE_JUDGE IN #endif scanf("%d",&t); while(t--) { scanf("%d%d%d%s",&n,&m,&k,s+1); printf("Case #%d: ",++cas); n<<=1; eg.clear(); memset(dp,-1,sizeof(dp)); for(int i=1;i<=n;) { int j=i+1; while(j<=n&&s[j]==s[i]) j++; eg.pb(j-i); i=j; } if(dfs(0,m)) printf("%c\n",s[1]); else printf("%c\n",s[1]=='A'?'B':'A'); } return 0; }
投递零跑科技等公司10个岗位 >