CF: Remove the Ends

CF: Remove the Ends

Problem - C - Codeforces

这题绝对不止1281分，估计1600+，但是疑似是赛时太多人开挂了导致评分过低。

思路1（TLE）：记忆化硬搜

直接记忆化硬搜，开个 unordered_map，注意要把 ​ l 和 ​ r 的状态通过编码来结合成一个 long long的数字来存，可惜第5个测试点TLE。

// Note: TLE
#include <bits/stdc++.h>
using namespace std;
static inline long long encodeState(int l, int r) {
    return ((long long)l << 32) | (unsigned int)r;
}

unordered_map<long long, long long> dpMemo;

vector<int> a;

long long dp(int l, int r) {
    if (l > r)
        return 0;
    long long key = encodeState(l, r);
    if (dpMemo.count(key))
        return dpMemo[key];
    long long best = -LLONG_MAX / 2;
    for (int i = l; i <= r; i++) {
        if (a[i] > 0) {
            best = max(best, (long long)a[i] + dp(i + 1, r));
        } else if (a[i] < 0) {
            best = max(best, (long long)(-a[i]) + dp(l, i - 1));
        }
    }
    dpMemo[key] = best;
    return best;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        a.resize(n + 1);
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        dpMemo.clear();
        long long ans = dp(1, n);
        cout << ans << "\n";
    }
    return 0;
}

思路2（AC）：左右递推合并

重新整理思路，看看有什么规律。

注意到，当数组 ​ a 全都是正的，那么最大化 ​ ans 的方式就是从左到右一个一个拿。这样的话， ​ ans=\sum^n_{i=0}a_i 。反之亦然（当 ​ a 全是负的就从右到左），然后还有一种情况是从左拿 ​ [0,i] 从右拿 ​ [i+1,n] 。

这样我们其实可以考虑开始分两个 ​ dp 数组去做，分为 ​ p\_dp 还有 ​ s\_dp ，就是prefix还有suffix的意思。 ​ p\_dp[i] 的含义就是从左到右拿正数直到拿完 ​ a[0...i] 最大的 ​ ans ：

第一步是说在遍历到 ​ i 的过程中，前面的 ​ 0...i-1 中保存好现有的最大值。同时要保证：

不然当 ​ a[i]>0 而 ​ p\_dp[i]\neq NEGINF 的时候，意味着光是进行prefix操作就能够拿完 ​ [0,i] ，但是这不可能因为 ​ a[i] 是负的它不能被prefix操作拿走，反之亦然。

第三步是把数组 ​ a 反过来好操作，不然从 ​ n 遍历到 ​ 0 也还是可以的。

现在我们知道了当 ​ a[n]>0 的时候， ​ p\_dp[n] 的答案，以及反过来 ​ s\_dp[n] 的答案。还有第三种情况，

最终答案，是三种情况中的最大值：

代码：

/*
 * Created by: Chixiyu
 * Date: 2025-02-17
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll NEG_INF = -1000000000000000000LL; // -1e18

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    // prefix
    vector<ll> prefix_dp(n + 1, NEG_INF);
    ll prefix_ans;
    ll prev_max = 0; // prevmax= max(a[0,i-1])
    prefix_dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] > 0) { // can prefix dp1
            prefix_dp[i] = max(prefix_dp[i], a[i] + prev_max);
            // update prev_max
            prev_max = max(prev_max, prefix_dp[i]);
        }
    }
    prefix_ans = prefix_dp[n];
    // suffix
    vector<ll> suffix_dp(n + 1, NEG_INF);
    ll suffix_ans;
    prev_max = 0;
    // inverse the array
    reverse(++a.begin(), a.end());
    suffix_dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] < 0) { // can suffix dp
            suffix_dp[i] = max(suffix_dp[i], -a[i] + prev_max);
            prev_max = max(prev_max, suffix_dp[i]);
        }
    }
    suffix_ans = suffix_dp[n];
    // calculate combined
    ll combined_ans = NEG_INF;
    for (int i = 0; i <= n; i++) {
        ll left = prefix_dp[i];
        ll right = 0;
        if (i != n) {
            right = suffix_dp[n - i];
        }
        combined_ans = max(combined_ans, left + right);
    }
    cout << max({prefix_ans, suffix_ans, combined_ans}) << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}