题目大意:
给定一个长为\(N (1 \leq N \leq 50)\)的序列,Bob 和 Alice 轮流从序列的最前端进行以下操作之一:
- 取出序列最前端的数,并将其加到自己的分数中;
- 取出序列最前端的数,将其加到对方的分数中,则下一轮可继续操作。
两人轮流操作直到序列被取完,分数多的一方获胜。
若两方都采用最佳策略,问在给定的情况下,两方最终的分数是多少。
题意分析:
我们先将题目简化,也就是不支持第二种操作,那么不难看出,此时两方的得分就与奇偶性有关。而支持操作一后,由于可以连续操作,此时奇偶性被改变,相当于双方将来的分数被交换了。所以我们只要求出此时双方将来的最优答案,并贪心地交换就可以了。我们从后向前遍历,并记录从\(i\)到\(n\)双方的最优答案,也相当于是当取到\(i\)时将来的答案。到一个新位置时,如果我们在获得当前的分数后还不如对方将来的分数,就直接交换两方的分数。最终代码十分简洁,复杂度\(O(N)\)。
AC代码
#include <bits/stdc++.h>
#define N 100050
using namespace std;
int n;
int a[N], p[5];//p记录双方当前以后的最优答案
int main(){
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = n; i >= 1; i--){
if(p[i + 1 & 1] > p[i & 1] + a[i])
swap(p[0], p[1]), p[i + 1 & 1] += a[i];
else p[i & 1] += a[i];
}
cout << p[0] << " " << p[1];
return 0;
}
标签:分数,Rules,题解,Pie,int,答案,两方,序列,操作 From: https://www.cnblogs.com/XHyair-blogs/p/18359714