对于下面的动态规划任务，如何处理这种情况?

Question

我在topcoder上尝试了一个简单的dp问题，它是这样的

彼得和斯努克正在玩合作纸牌游戏。游戏结束了使用特殊卡片:每张卡片上都标有一些正整数。卡片上的整数不一定是不同的。

游戏开始时，彼得手里拿着几张牌斯纳克手里拿着其他的牌。你得到了[]是彼得和鼻烟，它们描述了开始时的状态游戏:彼得的元素是彼得牌上的数字和snuke的元素是snuke牌上的数字。

在游戏中，玩家将把他们的一些牌放在一个堆。最初，这一堆是空的。球员们轮流上场转身，彼得先走。在每个回合中，如果当前玩家没有手握纸牌，游戏结束。否则，玩家必须做出选择正好一个有效的动作。有三种有效的招式牌堆是空的，玩家可以选择任意一张牌并将其放在堆。如果牌堆不是空的，玩家可以选择任意一张牌和把它放在最上面。然而，这个动作只有在新卡上的号码严格大于卡上的号码这是之前最重要的。玩家可能总是从他的卡片中挑一张吃掉。

peter和Snuke有一个共同的目标:他们想用as创建一堆尽可能多的卡片。返回堆的大小游戏，假设他们合作并最优地玩游戏。

I/O:

{2, 5}
{3, 1}
Returns: 3
One optimal way is as follows.
Petr puts 2 onto the pile.
Snuke puts 3 onto the pile.
Petr puts 5 onto the pile.
Snuke eats 1.
The game ends because Petr has no cards in his hand.
{1,1,1}
{1,1,1}
returns 1

我定义了一个dp函数，定义dp[i][j]为桌上彼得的ith牌和斯内克的jth牌的最大牌数，并尝试了以下代码:

for(int i=0;i<3;i++)
    {
        for(int j=0;j<3;j++)
        {
            if(i==0||j==0)
                dp[i][j]=1;
            else if(a[i]>b[j])
                dp[i][j] = max(dp[i-1][j]+1, dp[i][j-1]);
            else if(a[i]<b[j])
                dp[i][j]= max(dp[i-1][j], dp[i][j-1]+1);
            if(a[i]==b[j])
                dp[i][j] = dp[i-1][j-1]; //This does not work
        }
    }
    cout <<  dp[2][2];

为简单起见，我只尝试两个元素。如果卡片上的整数是不同的，这个解决方案就有效。我有点困惑，想出不明显的情况。相等整数的dp状态的定义是什么?

Answer 1

我认为应该先对两个玩家的元素进行递增排序，因为移动较小的值总是比移动较大的值好。

之后你dp:

F[i][j][u][v]是Petr的第i张牌和Snuke的第u张牌桌上的最大牌数，{j,v}={0,1}: j=0 => Petr吃了第i张牌，1 => Petr把第i张牌放在饼上。对于u, v也是一样。

然后

轮到彼得了:i>u:

F[我][0][美国][v] = max (F(张)[0][美国][v], F(张)[1][美国][v]);

F[我][1][美国][v] = max (F(张)[0][美国][v], F(张)[1][美国][v]) + 1,

Snuke的回合:i=u:

F[我][j][美国][0]= max (F[我][j] [u-1] [0], F[我][j] [u-1] [1]);

F[我][j][美国][1]= max (F[我][j] [u-1] [0], F[我][j] [u-1] [1]) + 1,

这是我的想法，我还没有尝试，但我希望它会帮助你!