题解

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;
const int INF = 0x3f3f3f3f;

int dp[N][N][2], n, m, p, harvest[N][N], f[N][N], cost[N], ans = -INF; 

int getMax(int x, int y) { return x > y ? x : y; }
int getMin(int x, int y) { return x < y ? x : y; }

int calculate(int i, int j, int k) 
{
    return f[i - 1][j - 1] - f[i - k - 1][j - k - 1];
}

int main() 
{
    memset(dp, -INF, sizeof(dp));
    cin >> n >> m >> p;
    for (int i = 1; i <= n; i++) 
    {
        for (int j = 1; j <= m; j++) 
        {
            cin >> harvest[i][j];
            f[j][i] = f[j - 1][i - 1] + harvest[i][j];
        }
    }
    for (int i = 1; i <= n; i++)
        cin >> cost[i];
    for (int i = 1; i <= n; i++)
        dp[1][i][0] = -cost[i];
    m++;

    for (int i = 2; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            for (int k = 1; k <= getMin(i, p); k++) 
            {
                if (j > k)
                    dp[i][j][1] = getMax(dp[i][j][1], dp[i - k][j - k][0] + calculate(i, j, k));
                else if (i > j)
                    dp[i][j][1] = getMax(dp[i][j][1], dp[i - k][n + j - k][0] + calculate(i - j + 1, n + 1, k - j + 1) + calculate(i, j, j - 1));
            }
        }
        for (int j = 1; j <= n; j++)
        {
            for (int k = 1; k <= n; k++) 
            {
                if (k == j) continue;
                dp[i][j][0] = getMax(dp[i][j][0], dp[i][k][1] - cost[j]);
            }
        }
    }

    for (int i = 1; i <= n; i++)
        ans = getMax(ans, dp[m][i][1]);

    cout << ans << endl;
    return 0;
}

加油，继续去肝下一题 ~