求助,测试点5后面的样例都通过不了
查看原帖
求助,测试点5后面的样例都通过不了
1024498
thatwall楼主2023/8/21 19:39
#include <iostream>
#include <map>
#include <utility>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>
#include <cstring>
#include <set>
#include <stack>
#include <climits>

#define ll long long
#define qc ios::sync_with_stdio(false); cin.tie(0);cout.tie(0)
using namespace std;
typedef pair<int, int> pii;

const int base = 1e9 + 7;
using bigint = struct bigint {
//    int base = 1e9 + 7;
    vector<int> inner;

    bigint() : inner(1, 0) {}

    bigint(int val) {
        inner.clear();
        while (val) {
            inner.push_back(val%base);
            val/=base;
        }
    }

    bigint(const bigint &ano) : inner(ano.inner.begin(), ano.inner.end()) {}

    bigint &operator=(int val) {
        inner.clear();
        while (val) {
            inner.push_back(val%base);
            val/=base;
        }
        return *this;
    }

    bigint &operator=(const bigint &ano) {
        inner.clear();
        inner.assign(ano.inner.begin(), ano.inner.end());
        return *this;
    }

    bigint operator+(int val) {
        bigint res(val);
        return *this+res;
    }

    bigint operator+(const bigint &ano) {
        bigint res(*this);
        int len = res.inner.size(), alen = ano.inner.size();
        int carry = 0;
        int i;
        for (i = 0; i < len && i < alen; ++i) {
            auto sum = res.inner[i] + ano.inner[i] + carry;
            res.inner[i] = sum % base;
            carry = sum / base;
        }
        while (i < len) {
            auto sum = res.inner[i] + carry;
            res.inner[i] = sum % base;
            carry = sum / base;
            ++i;
        }
        while (i < alen) {
            auto sum = ano.inner[i] + carry;
            res.inner.push_back(sum % base);
            carry = sum / base;
            ++i;
        }
        if (carry) {
            res.inner.push_back(carry);
        }
        return res;
    }

    bool operator<(const bigint &ano) {
        if (inner.size() == ano.inner.size()) {
            int len = inner.size();
            for (int i = len - 1; i >= 0; --i) {
                if (inner[i] < ano.inner[i]) {
                    return true;
                } else if (inner[i] > ano.inner[i]) {
                    return false;
                }
            }
            return false;
        }
        return inner.size() < ano.inner.size();
    }

};
bigint dp[201][201];

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param matrix int整型vector<vector<>>
     * @return int整型
     */
    int matrixScore(vector<vector<int> > &matrix) {
        int n = matrix.size(), m = matrix.front().size();
        long long sum = 0;
        for (int r = 0; r < n; ++r) {
            for (int k = 0; k < m; ++k) {
                for (int i = 0; i + k < m; ++i) {
                    int j = i + k;
                    if (j == i) {
                        dp[i][j] = (2 * matrix[r][i]);
                    } else {
                        auto head = dp[i + 1][j] + matrix[r][i], tail = dp[i][j - 1] + matrix[r][j];
                        if (head < tail) {
                            dp[i][j] = tail + tail;
                        } else {
                            dp[i][j] = head + head;
                        }
//                        dp[i][j] = 2 * max(dp[i + 1][j] + matrix[r][i], dp[i][j - 1] + matrix[r][j]);
                    }
                }
            }
            sum = (sum + dp[0][m - 1].inner.front()) % base;
        }
        return (int) sum;
    }
};

int main() {
    qc;
//    freopen("inputs.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    int n, m;
    cin >> n >> m;
    vector<vector<int> > matrix(n);
    for (auto &vec: matrix) {
        vec.resize(m);
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> matrix[i][j];
        }
    }
    cout << Solution().matrixScore(matrix) << endl;
    return 0;
}

2023/8/21 19:39
加载中...