题目来源：中山纪念中学

题目描述：

Alice想让Bob陪他去看《唐山大地震》，但由于Bob是个很感性的人，怕流泪不想去，但又不好意思以这个作为拒绝的理由，便提出玩一个游戏。
　　N个正整数围成一圈，规则如下：
　　•两个玩家轮流取数；
　　•最开始先手的玩家可以取任意一个数x；
　　•从第二步开始当前玩家只能取x（上一玩家刚刚取的数）左右两边相邻的数；
　　•直到取完所有的数，游戏结束；
　　•取得较多奇数的玩家获胜。
　　Bob为了显示大度，让Alice先取，但他忘了自己和Alice都是绝顶聪明之人，现在Alice请你帮他计算第一步有多少种取法使得最终获得胜利。

输入：

第一行包含一个整数N(1<=N<=100)，表示数的个数。第二行包含N个正整数，每个数都在1到1000之间，任意两个数互不相同。

输出：

输出Alice第一步有多少种取法。

输入样例：

输入1：
3
3 1 5

输入2：
4
1 2 3 4

输入3：
8
4 10 5 2 9 8 1 7

输出样例：

输出1：
3

输出2：
2

输出3：
5

思路：DP

听说这是博理论？噢~原来这就是博弈论

AC代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[210],f[210][210],s[210][210],anss; /*a[]：记录数据奇偶情况 f[i,j]：i到j区间先手能取到的最多奇数个数 s[i,j]:i到j区间的奇数个数*/
int main()
{
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        int b;
        cin>>b;
        if (b%2!=0) a[i]=1,a[i+n]=1; //偶数为0，奇数为1，因为是环，所以数组*2来循环 
    }
    for (int i=1;i<=n*2;i++)
      for (int j=1;j<=n*2;j++) 
        for (int k=i;k<=j;k++) s[i][j]+=a[k];   //走一遍i到j区间，累加此区间的奇数个数 
    for (int k=1;k<=n;k++) //从1~n枚举先手
    {
        for (int i=1;i<=n*2;i++) f[i][i]=a[i];//本身是奇数的话能取到1个奇数，就是自己
        for (int i=k+n-1;i>=k+1;i--)
          for (int j=i+1;j<=k+n-1;j++) 
            f[i][j]=max((s[i][j]-f[i+1][j]),(s[i][j]-f[i][j-1]));
        if (s[k+1][k+n]-f[k+1][k+n-1]>f[k+1][k+n-1]) anss++;
    }
    cout<<anss<<endl;
    return 0;
}