脚本宝典收集整理的这篇文章主要介绍了Pokémon Army (easy version),脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
题目链接
题意:
给你(n)个元素,你可以选其中(k)个元素构成一个子集(b),子集的元素会以(b_1-b_2+b_3-b_4cdots)的方式求和,问你怎样选让和最大
本题可以从dp的角度去分析,对于一个元素,我们有三种选择:不选,加上此元素,减去此元素。
这样本题就可以构成一个状态机dp,情况如下:
这样我们就可以在(O(n))的复杂度下完成本题的dp计算了
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 3e5 + 1000;
typedef long long LL; // 注意爆int
int a[N], n;
LL f[N][2];
int main()
{
io;
int _t, q;
scanf("%d", &_t);
while (_t --)
{
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++)
{
f[i][0] = f[i - 1][0];
f[i][1] = f[i - 1][1];
f[i][0] = max(f[i][0], f[i - 1][1] + a[i]);
f[i][1] = max(f[i][1], f[i - 1][0] - a[i]);
}
cout << max(f[n][0], f[n][1]) << 'n';
}
return 0;
}
以上是脚本宝典为你收集整理的Pokémon Army (easy version)全部内容,希望文章能够帮你解决Pokémon Army (easy version)所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。