题目链接：这里
Description

There was an interesting game played on a popular Korean reality TV Show. 12 players in 3 teams
— 4 persons in each team — lined up in one row in random order. The game master approaches the
players one by one starting from the most front player, with a tray full of 31 cakes. Each player should
eat at least 1 and at most 5 cakes during his/her turn. The player who eats the last cake will lose
along with his/her group (this is a team game). It was more an entertainment show rather than a real
competition. The players were selected from “chubby” celebrities who like to eat, thus causing them
in dilemma whether they should win the game (which might require them to hold their urge to eat the
cakes), or just enjoy all 5 cakes ignoring their team member.
This problem is related to the game. There are 2 teams (A and B) each with N players lined up
in a row in random order. Initially there are M cakes in the tray, and each player (starting from the
most front) has to eat at least 1 and at most K cakes during his/her turn. The team whose player eat
the last cake win (note that this is different compared to the original game).
Your task is to determine which team will win the game, given both teams play optimally.
Input

The first line of input contains an integer T (T ≤ 100) denoting the number of cases. Each case begins
with three integers N, M, and K (1 ≤ N ≤ 1, 000; 1 ≤ K ≤ M ≤ 2 ∗ N) in a line denoting the number
of players in each team, the initial number of cakes, and the maximum number of cakes can be eaten
by each player in his/her turn respectively. The next line contains a string S representing the players
order from the front most to the last player. S consists of only character ‘A’ or ‘B’ representing which
team does the respective player belongs to. The length of S is exactly 2 ∗ N and the number of ‘A’ and
‘B’ will be equal.
Output

For each case, output ‘Case #X: Y ’, where X is the case number starts from 1 and Y is ‘A’ if the
game will be won by team A, otherwise ‘B’. Assume both teams will play the game optimally to win
the game.
Explanation for 1st sample case:
The first two players of team A each needs to eat 2 cakes, while the third A player eats the last
cake.
Explanation for 2nd sample case:
No matter what team A do, the last cake will be eaten by one of team B’s player.
Explanation for 3rd sample case:
To ensure their win, the first player (B) should eat 2 cakes, leaving only 3 cakes to the next player
(A). This player (A) should eat at least 1 and at most 2 cakes. No matter how many cakes this player
eats, the next player (B) will eat the last cake.
Sample Input

4
3 5 2
AAABBB
4 7 2
AAABBBBA
4 5 2
BABABABA
4 6 3
BAABBABA
Sample Output

Case #1: A
Case #2: B
Case #3: B
Case #4: A

题意：AB 两队吃蛋糕,每个队n个人,共有m块蛋糕,每人至少吃一块蛋糕, 最多吃k块蛋糕,哪个队伍吃到最后一块就算获胜,问你谁能胜利
解法：首先,把连着的A或者B给合并了,合并以后记录一下A和B在当前位置。的个数有多少,然后我们就可以用当前位置的A/B的个数*k得到这个，位置吃蛋糕的数量范围。接下来就是记忆化搜索,尝试每种状态下是否有可能发展成使得下一位为必败态。

//UVALIVE 6913

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2100;
int dp[maxn][maxn];
int n, m, k;
char str[maxn];
int v[maxn];
int dfs(int u, int shengxia){
    if(dp[u][shengxia] != -1) return dp[u][shengxia];//如果当前状态在前面已经出现过,直接返回
    if(shengxia <= v[u]*k) return dp[u][shengxia] = 1; //如果剩余的蛋糕比当前的人能吃的少,那么当前状态是必胜态
    dp[u][shengxia] = 0;//否则暂定当前状态为必败态,再往后搜索,如果找到能必胜,则改为必胜返回
    for(int i = v[u]; i <= k*v[u]; i++)//搜索当前位所有吃蛋糕的数量
        if(dfs(u+1, shengxia-i) == 0) //如果下一位为必败态,则当前态改为必胜态返回
            return dp[u][shengxia] = 1;
    return dp[u][shengxia];//找不到必胜态也要记得返回
}

int main(){
    int T, ks = 0; scanf("%d", &T);
    while(T--){
        memset(dp, -1, sizeof(dp));
        memset(v, 0, sizeof(v));
        scanf("%d%d%d", &n, &m, &k);
        scanf("%s", str);
        int cnt = 0, flag = 1;
        for(int i = 1; i < 2*n ; i++){
            if(str[i] == str[i-1]) flag++;
            else{
                v[cnt++] = flag;
                flag = 1;
            }
        }
        v[cnt++] = flag;
        printf("Case #%d: ", ++ks);
        if(dfs(0, m)) puts(str[0] == 'A' ? "A" : "B");
        else puts(str[0] == 'A' ? "B" : "A");
    }
    return 0;
}