CF-1389B Array Walk 题解

题目大意

给你一个数组，你从第一个位置开始走，每次可以选择向左走或者向右走，你最多有z次向右走的机会，最多走k步，你踩到的数字算你获得的积分，问你最多获得多少积分。

解题思路

DP题。

设$dp[i] [j]$表示在位置i处，已经用了j次左移机会的最大值。

从左边转移的值为$dp[j-1][i]+num[j]$，从右边转移的值为$dp[j+1][i-1]+num[j]$。

需要注意当j在位置最右边的时候不能从右边转移。

这个答案取的就很妙。

当$j-1+2*i$的值等于m时更新最大值。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <deque>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
#define rep(i,a,n) for (ll i=a;i<=n;i++)
#define per(i,a,n) for (ll i=n;i>=a;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define mp(x,y) make_pair(x,y)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define bg begin
#define rbg rbegin
#define ed end
#define dbg(x) cout << #x << "===" << x << endl
typedef double db;
typedef long long ll;
typedef unsigned long long ull;

const int N = 1e5 + 5;
ll dp[N][6];
int num[N];

int gcd(int a, int b) {
	return !b ? a : gcd(b, a % b);
}

ll qpow(ll a, ll b) {
	ll ans = 1;
	while (b) {
		if (b & 1)	ans *= a;
		a <<= 1, b >>= 1;
	}
	return ans;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	//freopen("D:\\测试用\\in.txt", "r", stdin);
	//freopen("D:\\测试用\\out.txt", "w+", stdout);
	int t; cin >> t;
	while (t--) {
		int n, k, z;
		cin >> n >> k >> z;
		rep(i, 1, n)	cin >> num[i];
		ll ans = 0;
		rep(i, 0, z) {
			rep(j, 1, n) {
				dp[j][i] = dp[j - 1][i] + num[j];
				if (i && j != n)	dp[j][i] = max(dp[j][i], dp[j + 1][i - 1] + num[j]);
				if (j - 1 + 2 * i == k)	ans = max(ans, dp[j][i]);
			}
		}
		cout << ans << endl;
	}
	return 0;
}