2016 UESTC Training for Dynamic Programming P – 柱爷的矩阵 矩阵、递推

首先，对于每一行数字，B[i]越大数值减小越快

如果取第i行和第j行的数字，且B[i]>B[j]，那么一定先取第i行。

所以先按照B[i]降序排序。

dp[i][j] 表示取了第i列第j行数字时的最优解

dp[i][j] = maxdpi_1[i-1][j-1] + max(0, val[i].a - (j-1)*val[i].b);
maxdpi_1[i][j] = max(maxdpi_1[i-1][j], dp[i][j]);

ans = {maxdpi_1};

复杂度 O(M*N);

#include 
#include 
#include 
using namespace std;
const int maxn = 1000 + 8;

int dp[maxn][maxn], maxdpi_1[maxn][maxn];

struct ab{
    int a, b;
} val[maxn];

bool cmp(const ab& x, const ab& y)
{
    return x.b > y.b;
}

int main()
{
    #ifdef LOCAL
    freopen("a.txt", "r", stdin);
    #endif // LOCAL
    int N, M, ans = 0;
    scanf("%d%d", &N, &M);
    for(int i = 1; i <= N; i++)
        scanf("%d", &val[i].a);
    for(int i = 1; i <= N; i++)
        scanf("%d", &val[i].b);
    sort(val + 1, val + N + 1, cmp);
    for(int j = 1; j <= M; j++){
        for(int i = 1; i <= N; i++){
            dp[i][j] = maxdpi_1[i-1][j-1] + max(0, val[i].a - (j-1)*val[i].b);
            maxdpi_1[i][j] = max(maxdpi_1[i-1][j], dp[i][j]);
        }
    }
    for(int j = 1; j <= M; j++) ans = max(ans, maxdpi_1[N][j]);
    printf("%d", ans);
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx