题目分析
题意:
给你(n)个元素,你可以选其中(k)个元素构成一个子集(b),子集的元素会以(b_1-b_2+b_3-b_4cdots)的方式求和,问你怎样选让和最大
本题可以从dp的角度去分析,对于一个元素,我们有三种选择:不选,加上此元素,减去此元素。
这样本题就可以构成一个状态机dp,情况如下:
graph LR
Enter("入口")
Exit("出口")
A("不选")
B("加上")
C("减去")
Enter --> A --> C
A --> B
B --> C --> Exit
C --> B --> Exit
B --> A
C --> A
- 状态表示(f(i,j)):
- 集合:所有选前(i)个物品,且状态为(j)的集合
- 属性:Max
- 状态计算:
- 对于不选:(f(i,j)=f(i-1,j)) 直接从上个元素对应的状态转移过来即可
- 对于加上此元素:(f(i,0)=max{(f(i-1,1)+w_i)}) 加上当前元素必定是从减去上一个元素转移过来
- 对于减去此元素:(f(i,1)=max{(f(i-1,0)+w_i)}) 同上
这样我们就可以在(O(n))的复杂度下完成本题的dp计算了
AC代码
#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]) << '
';
}
return 0;
}