小米 oj 硬币比赛（思维＋动态规划）

 硬币比赛

序号：#47难度：困难时间限制：1000ms内存限制：10M

描述

有 n 个不同价值的硬币排成一条线。有 A 与 B 两个玩家，指定由 A 开始轮流（A 先手，然后 B，然后再 A..）从左边依次拿走 1 或 2 个硬币（不能不拿，也不能拿其他个数），直到没有硬币为止。最后计算 A 与 B 分别拿到的硬币总价值，价值高的人获胜。

请依据硬币的排列情况来判定，先手的玩家 A 能否找到必胜策略？

输入

使用逗号(,)分隔的一个正整数数组，表示这排硬币的排列情况与对应价值

输出

true 或 false（字符类型），表示玩家 A 能否找到必胜策略

输入样例

1,2,2

1,2,4

复制样例

输出样例

true

false

这道题真巧妙啊！！需要逆向思维来想，用动态规划的思想来做。

设dp[i]为考虑下标从i到n的子数组中若A先取,B也采取最优策略时，Ａ能取到的最大值，

则最终A是否有必胜策略等价于 dp[0]*2是否>原数组的sum。（Ａ能取大于总数的一半，

则Ａ必胜）

状态转移方程为: dp[i]=max(a[i]+min(dp[i+2],dp[i+3]),a[i]+a[i+1]+min(dp[i+3],dp[i+4]));

上式中取min运算符是由于，对于A的两种取法,B的取法则是自己取后使得A能得到的价值

最小的方案。

参考代码:

#include<bits/stdc++.h>

using namespace std;

int read(char *buf,int* num)

{

    int cnt=0;

    int  v;

    char *p = strtok(buf,",");

    while(p)

    {

        sscanf(p,"%d",&v);

        num[cnt++]=v;

        p = strtok(NULL,",");

    }

    return cnt;

}

char buf[1000005];

int a[10005];

int dp[10005];

int n;

int main()

{

    while(~scanf("%s",buf))

    {

        n=read(buf,a);

        memset(dp,0,sizeof(dp));

        int sum=0;

        for(int i=0;i<n;i++)sum+=a[i];

        if(n<=2){puts("true");continue;}

        else{

            dp[n-1]=a[n-1];

            dp[n-2]=a[n-2]+a[n-1];

            dp[n-3]=a[n-3]+a[n-2];

            for(int i=n-4;i>=0;i--)

            {

          dp[i]=max(a[i]+min(dp[i+2],dp[i+3]),a[i]+a[i+1]+min(dp[i+3],dp[i+4]));

            }

        }

        if(2*dp[0]>sum)puts("true");

        else puts("false");

    }

    return 0;

}