为防止广告，目前nocow只有登录用户能够创建新页面。如要创建页面请先登录/注册（新用户需要等待1个小时才能正常使用该功能）。
USACO/game1
目录 |
[编辑] 分析1
博弈问题，可以用动态规划解决
设sum[i][j]表示从i到j的所有数字和，dp[i][j]表示从i到j这部分的先取者能获得的最大数字和
dp[i][j]=sum[i][j]-min(dp[i][j-1],dp[i+1][j]);
以i~j的区域的长度作为阶段即可。
详细见C++代码(ybojan2)
[编辑] 分析2
博弈问题，可以使用动态规划求解。
状态定义：用F[i,j]表示第一个玩家先取时（貌似应该是某个玩家先取时能获得的最高分），在第i到第j的子序列中能拿到的最高分；用S[i][j]表示第i到第j的子序列中所有数字的和；用num[i]表示第1到第n的序列中第i个数。
边界条件：F[i][i]=num[i]
状态转移方程：
F[i][j]=max{num[i]+S[i+1][j]-F[i+1][j],num[j]+S[i][j-1]-F[i][j-1]}
结果
p1=F[1][n];
p2=S[1][n]-F[1][n];
解析：
num[i]+S[i+1][j]-F[i+1][j]表示的是，p1拿第i到第j最左边的数，然后轮到p2在第i+1到第j的序列中先取，会剩下S[i+1][j]-F[i+1][j]，这些归p1。
路人甲：话说num[i]+S[i+1][j]不就等于S[i][j]么，这跟分析1木有任何区别啊。。。
[编辑] 分析3
令
F(start,stop) 表示当前游戏者面对编号从start到stop的数字时可以得到的最大收益 Sum(i,j) 表示编号i到j的数字和
可知
F(start,stop)=Max( Sum(start+1,stop)-F(start+1,stop)+num[start] ,Sum(start,stop-1)-F(start,stop-1)+num[stop] );
边界条件
F(start,start)=num[start];
F(1,N) Sum(1,N)-F(1,N) 即为所求解
[编辑] 分析4
当你在i到j中取了i之后,那么你就只能在i + 1到j中作为后手取值,故你所能取得的值为i + 1到j的和减去作为先手所取得的最大值;
初始化
f[i][i] = sum[i][i] = a[i];
状态转移方程:
f[i][j] = max(a[i] + sum[i + 1][j] - f[i + 1][j], a[j] + sum[i][j - 1] - f[i][j - 1]);
f[i][j] 表示在从第i个数到第j个数里先手能取得的最大值;
a[i] 表示第i个数的值;
sum[i][j] 表示在从第i个数到第j个数的和;
--Nettle99 19:21 2009年2月1日 (CST)
[编辑] 分析5
同样DP，d[i][j].c表示从i到j能取到的最大值，d[i][j].p、d[i][j].q表示从i到j用最优取法取数以后剩下数据的上下限
转移:
c1 = d[i][i].c+d[ d[i+1][j].p ][ d[i+1][j].q ].c 从前面取，对手从i+1，j中取，取完剩下d[i+1][j].p到d[i+1][j].q
c2 = d[j][j].c+d[ d[i][j-1].p ][ d[i][j-1],q ].c 从后面取，对手从i，j-1中取，取完剩下d[i][j-1].p到d[i][j-1].q
if (c1>c2){ d[i][j].c=c1; d[i][j].p = i+1; d[i][j].q = j;}
else { d[i][j].c=c2, d[i][j].p = i; d[i][j].q = j-1;}
初始化：
d[i][i].c为初始数据的第i个数，d[i][i].p=d[i][i].q=0
d[0][0].c = 0
输出结果d[1][N].c d[ d[1][N].p ][ d[1][N].q ]
[编辑] 分析6
我的方法:同样也是动态规划，但是转移方程不一样，可以省去计算序列和的total数组 f[i][j]表示在序列i~j中，序列长度为偶数时取数的人所能得到的最大分数，也就是说当最初总序列长为偶数时，f表示的就是第一个玩家 在i~j中所能获得的最高分，若最初总序列长为奇数时，f表示的就是第二个玩家在i~j中所能获得的最高分。则转移方程为 if((j-i+1)%2)
f[i][j] = min(f[i+1][j],f[i][j-1]); //长度为奇数时，对方肯定要按照对手取分最少的方式取，以让自己拿高分
else
f[i][j] = max(f[i+1][j]+board[i], f[i][j-1]+[board[j]); //长度为偶数时，偶数玩家按照自己拿最高分的方式取
