NC12986K

Solution

遇到比较困难的题目可以先从比较暴力的方法开始入手在结合题目的一些性质、数据范围开始进行优化。
思考一下能够想到比较暴力的dp:

: 表示第 行选了 列，一共选了 个数的最大值。

按上述式子写复杂度是 毫无疑问会TLE、MLE，接着开始优化，我们降一维则可以通过本题。

仔细观察发现我们可以把 提到 max 函数外面。
时间：我们可以通过后缀最大值来优化这个式子，每次对当前行求完的同时进行后缀最大值。
空间：滚动数组

时间复杂度:

坑点：一定要清空 ， 因为不清空的话 是上上一行的后缀最大值，他的列是对不上的。

Code

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ls (p << 1)
#define rs (ls | 1)
#define tm ((tl + tr) >> 1)
#define lowbit(x) ((x) & -(x))

using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

constexpr double eps = 1e-8;
constexpr int NINF = 0xc0c0c0c0;
constexpr int INF = 0x3f3f3f3f;
constexpr ll LNINF = 0xc0c0c0c0c0c0c0c0;
constexpr ll LINF = 0x3f3f3f3f3f3f3f3f;
constexpr ll mod = 1e9 + 7;
constexpr ll N = 300 + 5;

int n, m, c;
ll f[2][N][1005], pre[N][N];

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

    cin >> n >> m >> c;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int x;
            cin >> x;
            pre[i][j] = pre[i][j - 1] + x;
        }
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        int cur = i & 1;
        memset(f[cur], 0, sizeof(f[cur]));
        for (int j = m; j >= 1; j--) {
            for (int k = i * j; k <= c; k++) {
                f[cur][j][k] = max({f[cur][j][k], f[cur ^ 1][j][k - j] + pre[i][j], f[cur][j + 1][k]});
            }
            ans = max(ans, f[cur][1][c]);
        }
    }
    cout << ans << '\n';

    return 0;
}