ZeroJudge F314: Warriors

The input is an N×M sized array, where each cell contains an integer between -100 and 100, representing the experience points accumulated by passing through that cell. You can start from any position in the top row and end at any position in the bottom row. During the process, you can move left, right, or down, but you cannot revisit any cell you've already passed through. Calculate the maximum total experience points you can obtain (which may be negative).

Sample Inputs/Outputs

Thought Process

Store the data in a 2D array called "v", and declare three more 2D arrays: "answer", "left prefix sum", and "right prefix sum". After collecting the data, especially check the left and right prefix sums for the first row. When performing prefix sum operations, it's essential to handle cases where there are preceding negative values. To address this, initialize a variable "sum" to v[0][0], and then update it as sum = max(0, sum) + v[0][i]. This ensures that the prefix sum considers whether the previous sum is negative and adds the larger value to the prefix sum. Set the "answer" for the first row to the maximum value between its left and right prefix sums.

Run a for loop from 1 to N-1 (excluding the 0th row, as it was already checked), and compute the left and right prefix sums. The difference this time is that you need to consider cases where you move from the previous row to the current row. If the evaluation encounters a boundary (i.e., the first or last position), set the prefix sum at that position to "the answer at the previous row's position" + "v[i][j]". Otherwise, set the prefix sum at that position to max(previous position's prefix sum, answer at the previous row's position + v[i][j]).

When outputting, print the "maximum value" of the "answer array" for the last row.

Sample Code－ZeroJudge F314: Warriors

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, M;
vector<vector<int>>v, ans, lprefix, rprefix;

vector<int> l1prefix() {
    int sum = v[0][0];
    vector<int>l;
    l.push_back(sum);
    for (int i = 1; i<M; i++) {
        sum = max(0 , sum) + v[0][i];
        l.push_back(sum);
    }
    return l;
}

vector<int> r1prefix() {
    int sum = v[0][M-1];
    vector<int>r;
    r.push_back(sum);
    for (int i = M-2; i>=0; i--) {
        sum = max(0 , sum) + v[0][i];
        r.push_back(sum);
    }
    reverse(r.begin(), r.end());
    return r;
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    for (int i = 0; i<N; i++) {
        vector<int>hi, qq;
        int sum = 0;
        for (int j = 0; j<M; j++) {
            int tmp;
            cin >> tmp;
            hi.push_back(tmp);
            qq.push_back(0);
            sum += tmp;
        }
        lprefix.push_back(qq);
        rprefix.push_back(qq);
        ans.push_back(qq);
        v.push_back(hi);
    }
    const vector<int> l = l1prefix(), r = r1prefix();
    for (int i = 0; i<M; i++) ans[0][i] = max(l[i], r[i]);
    for (int i = 1; i<N; i++) {
        for (int j = 0; j<M; j++) {
            if (j == 0) lprefix[i][j] = ans[i-1][j] + v[i][j];
            else lprefix[i][j] = max(lprefix[i][j-1], ans[i-1][j]) + v[i][j];
        }
        for (int j = M-1; j>=0; j--) {
            if (j == M-1) rprefix[i][j] = ans[i-1][j] + v[i][j];
            else rprefix[i][j] = max(rprefix[i][j+1], ans[i-1][j]) + v[i][j];
            ans[i][j] = max(lprefix[i][j], rprefix[i][j]);
        }
    }
    cout << *max_element(ans[N-1].begin(), ans[N-1].end()) << "\n";
}

//ZeroJudge F314
//Dr. SeanXD