1

我正在尝试解决topcoder 上的 Ball Removal 问题，将问题声明粘贴到此处，因为需要登录才能访问此链接。

问题陈述

你有 N 个球，其中 N 是奇数。球的编号从 0 到 N-1。按此顺序，它们从左到右排列成一排。

除了数字之外，每个球上都写有“左”字或“右”字。为简单起见，我们将使用字符“<”代替“left”，使用字符“>”代替“right”。您将获得所有球上的标签作为字符串标签。对于每个 i，label 的字符 i 代表球 i 上的单词。

您现在将重复以下过程：

  • 选择一个不在球排两端的球。
  • 如果选择的球有标签'<'，删除选择的球和紧邻它左边的球。否则，删除选定的球以及它右侧的球。
  • 在不重新排列剩余的球的情况下，将它们推在一起以消除上一步中产生的间隙。

当该行中只剩下一个球时，该过程结束。那个球叫做幸存者。请注意，球上的数字在此过程中不会改变。

找到所有可能的幸存者。您的方法必须返回一个正好包含 N 个字符的字符串。如果球 i 可以是幸存者，则返回值的字符 i 必须是 'o'（小写 oh）。否则，对应的字符必须是'.' （一段时间）。

约束

  • 标签将包含 3 到 49 个字符（包括 3 到 49 个字符）。
  • 标签将包含奇数个字符。
  • 标签的每个字符将是“>”或“<”。

示例
"<<>" 返回："..o"

最初，你有三个球。由于您无法选择行尾的球，因此您必须选择球 1。由于其标签为“<”，因此您删除了球 0 和 1。因此唯一可能的幸存者是球 2。1) >>>< <" 返回："o...o"

如果先选2球或3球，接下来要选1球，幸存者是0号球。如果先选1号球，接下来要选3号球，幸存者是4号球。

2) "<<><<" 返回："..o"

3) "<><<><>" 返回："o.....o"

4) >>><<<>>>>><<<>" 返回："o.....oo..o"

我正在考虑一种动态编程方法来解决这个问题，我正在考虑使用一个布尔数组来标记哪些字符已被删除，然后找到下一个左边和下一个右边，但这使得该方法效率非常低，我必须写一个递归方法。为了实现动态编程方法，我需要维护一个状态。但是我无法弄清楚我应该保持什么状态，在我看来，状态是当前字符串和当前索引的组合，但是维护状态字符串对我来说似乎不正确。

我面临的另一个问题是，在这种情况下，如果我改变方向，结果也会改变，如果我从左向右移动，我可能也需要从右向左移动。请帮助我找到解决此问题的正确方法。

4

1 回答 1

1

状态可以是布尔值 - DP[left][right][isLeftBoundary][isRightBoundary]。

这意味着如果可以完全消除开始于left和结束于的子字符串。right

isLeftBoundaryleft如果符号是字符串的最左边，则只是一个布尔标志。

isRightBoundaryright如果符号是字符串的最右边，则只是一个布尔标志。

ifDP[0][i - 1][1][0]和DP[i + 1][N][0][1]are true，表示该位置的球i可以保留。

    int canDelete(int l, int r, int st, int en)
    {
        if (l > r) return 1; //we succeeded in removing the whole string

        if (DP[l][r][st][en] != -1)
           return DP[l][r][st][en];

        int ans = 0;

        //i is the last removed ball, which will eliminate the whole string[l, r]
        for (int i = l + st; i <= r - en; i++) 
        {
            if (inp[i] == '<') //it will remove a ball to the left, but which one?
            {
                for (int j = l; j < i; j++) //ball i will remove ball j
                {       
                     if (canDelete(l, j - 1, st, 0) 
                      && canDelete(j + 1, i - 1, 0, 0) 
                      && canDelete(i + 1, r, 0, en))
                         ans = 1;       
                }
            }
            else
            if (inp[i] == '>') //it will remove a ball to the right, but which one?
            {
                for (int j = i + 1; j <= r; j++) //ball i will remove ball j
                {       
                     if (canDelete(l, i - 1, st, 0) 
                      && canDelete(i + 1, j - 1, 0, 0) 
                      && canDelete(j + 1, r, 0, en))
                         ans = 1;       
                }       
            }
        }

        return ans;
    }
于 2012-11-29T08:13:20.717 回答