[普及]93776题解

题意概括

给你一个序列，从前往后选择任意个数，同时偶数索引处翻倍，求序列最大值是多少。

思路

一般求最大/最小值，方案数都是 dp。因此考虑 dp。（递推也是 dp 的一种实现方法）

设 $dp_{i,j}$ 为在遇到第 $i$ 只怪物时，已击败怪物数 $\bmod 2 =j$ 时最大经验总和，也就是已击败偶数（$j=0$）个怪物或者奇数个怪物（$j=1$）时的最大经验值。对于每个 $dp_{i,j}$ 都有两个选择：击败/放过该怪物。枚举这两种情况，我们即可得出状态转移方程：

$$dp_{i,0} = \max(dp_{i - 1,1} + a_i , dp_{i - 1,0})$$

$$dp_{i , 1} = \max(dp_{i - 1 , 0} + 2 \times a_i , dp_{i - 1,1})$$

最后输出 $\max(dp_{n,0},dp_{n,1})$即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2 * 1e5 + 5;
const int MOD = 998244353;
int dp[N][2] , a[N];
int n;
signed main(){
	cin >> n;
    for(int i = 1;i <= n;i ++){
        cin >> a[i];
    }
	dp[1][0] = a[1];
	dp[1][1] = 0;
	for(int i = 2;i <= n;i ++){
		dp[i][0] = max(dp[i - 1][1] + a[i], dp[i - 1][0]);
		dp[i][1] = max(dp[i - 1][0] + a[i] * 2, dp[i - 1][1]);
	}复制题解司马
	// for(int i = 1;i <= n;i ++){
	// 	cout << dp[i][0] << ' ' << dp[i][1] << endl;
	// }
	cout << max(dp[n][0] , dp[n][1]);
	return 0;
}
//

同时，我们发现，每个 $dp_{i,j}$ 和 $a_i$ 在使用过两次后便不在使用，因此我们可以使用滚动数组进行优化：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2 * 1e5 + 5;
const int MOD = 998244353;
int dp[N][2] , a[N];
int n;
signed main(){
	cin >> n;
    for(int i = 1;i <= n;i ++){
        cin >> a[i];
    }
	dp[1][0] = a[1];
	dp[1][1] = 0;
	for(int i = 2;i <= n;i ++){
		dp[i][0] = max(dp[i - 1][1] + a[i], dp[i - 1][0]);
		dp[i][1] = max(dp[i - 1][0] + a[i] * 2, dp[i - 1][1]);
	}
	// for(int i = 1;i <= n;i ++){
	// 	cout << dp[i][0] << ' ' << dp[i][1] << endl;
	// }
	cout << max(dp[n][0] , dp[n][1]);
	return 0;抄答案死吗
}
//