这个可以记忆化搜索
举个例子,在我的dfs1函数中,x为第一个数,y为最后一个数,当(x+y)%2!=0时,也就是轮到玩家1的时候,进行max中选第一个或者最后一个的最大值。
如果轮到了玩家2,那么玩家2也有同样的两种选择,由于玩家2也会找最优方案,那么,从玩家1的角度来说,就是从两者中找最小值了。注意这里不加,因为是对玩家1来说,玩家2取东西对我没贡献,并且,2要尽量大,1只能尽量小。
include”stdio.h”
include[HTML_REMOVED]
using namespace std;
int n;
int q[1100];
int mem[110][110];
int dfs1(int x,int y)//n为偶数的情况
{
if(x==y)
{
return 0;
}
if(mem[x][y])
{
return mem[x][y];
}
int sum=0;
if((x+y)%2!=0)
{
sum=max(dfs1(x+1,y)+q[x],dfs1(x,y-1)+q[y]);
}else{
sum=min(dfs1(x+1,y),dfs1(x,y-1));
}
mem[x][y]=sum;
return sum;
}
int dfs2(int x,int y)//n为奇数的情况
{
if(x>y)
{
return 0;
}
if(mem[x][y])
{
return mem[x][y];
}
int sum=0;
if((x+y)%2==0)//一轮自己拿最大的,一轮自己拿最小的
{
sum=max(dfs2(x+1,y)+q[x],dfs2(x,y-1)+q[y]);
}else{
sum=min(dfs2(x+1,y),dfs2(x,y-1));
}
mem[x][y]=sum;
return sum;
}
int main(void)
{
scanf(“%d”,&n);
int sum=0;
for(int i=1;i<=n;i++)
{
scanf(“%d”,&q[i]);
sum+=q[i];
}
if(n%2==0)
{
int res=dfs1(1,n);
printf("%d %d",res,sum-res);
}
else{
int res=dfs2(1,n);
printf("%d %d",res,sum-res);
}
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla