---

C. Card Game

原创 于 2023-09-27 20:59:27 发布 · 粉丝可见 · 312 阅读 · 1 · 0 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/133363635

题目：

样例：

cobol<br/>4<br/>4<br/>-4 1 -3 5<br/>4<br/>1 -2 3 -4<br/>3<br/>-1 3 -5<br/>1<br/>-1<br/>

5 4 2 0

思路：

这里的题意就是，

当我们 i 取奇数的时候，可以获得该奇数 i 的值，并去掉当前卡牌。

当我们 i 取偶数的时候，去掉当前卡牌。

这里我们去掉当前卡牌后，后面的卡牌下标 i 就会变化，后面的 i 的奇偶性就会变化。

所以当我们一个一个从后面开始取数的时候，就可以巧妙的避开这些变化，之后就是贪心操作。

代码详解如下：

#include <iostream>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#define endl '\n'
#define int long long
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#define uset unordered_set
#pragma GCC optimize(3,"Ofast","inline")
#define ___G std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;

inline void solve()
{	
	int n;
	cin >> n;

	umap<int,int>a;	// 存储卡牌数值

	for(int i = 1;i <= n;++i)
	{
		cin >> a[i];
	}

	// now 是取得的值多少
	int now = 0,ans = 0;

	// 开始贪心取值
	// 从后面开始取值，是因为当我们取一个 i 值后
	// 后面的 下标 i 就会变化，我们从后面 i 开始取值
	// 巧妙的避开这些变化
	for(int i = n;i > 0;--i)
	{
		// 当我们取得的 i 是偶数的时候
		if(i % 2 == 0)
		{
			// 更新我们的ans 
			ans = max(ans,now);
		}else
		{
			// 当我们取的 i 是奇数的时候，说明当前的 a[i] 也是可取的
			// 继续更新 ans
			ans = max(ans,a[i] + now);
		}
		
		// now 取值，我们只取 >= 0 更好的数值
		now += max(a[i],(int)0);
	}
	
	// 输出答案
	cout << ans << endl;
}

signed main()
{
//	freopen("a.txt", "r", stdin);
	___G;
	int _t = 1;
	cin >> _t;
	while (_t--)
	{
		solve();
	}
	return 0;
}

最后提交：