小气鬼送礼物算法优化-（2020阿里笔试题）

相思不扫积久弥厚

发布于 2023-10-26 14:25:40

1280

发布于 2023-10-26 14:25:40

文章被收录于专栏：用户10805953的专栏用户10805953的专栏

原解在：http://www.linhui.fun/article/47

题面是一个装逼小气鬼送礼物，他有一个架子，有n排礼物（每个礼物有自己的权值c，c越大礼物越贵），他要送m个礼物出去，但是他又不想送最贵的m个又想装大方，所以他给自己立了个规矩，每次选礼物都只能从任意一排的两端选择，问他最贵能送多少权值出去？

输入格式：第一行输入n，m ，下面n行每行输入一个x代表这一行有x个礼物，后面跟x个数字，每个数字代表这个位置的礼物的权值。

输出：一个数字，代表最贵的权值。

发现计算b数组的时候也可以动态规划算，并且可以优化为一维。

另外算dp数组的时候不需要复制，也不需要遍历到m（到本行最大数量即可）

#include <iostream>
#include<stdio.h>
int c[105];
int b[105];
int dp[10005];
int main() {
    int n, m, x;
    scanf("%d%d", & n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%d", & c[0]);
        for (int j = 1; j <= c[0]; j++) {
            scanf("%d", & x);
            c[j] = j > 1 ? c[j - 1] + x : x;
            for (int k = j; k >= 1; k--) {
                b[k] = b[k - 1] + x > c[k] ? b[k - 1] + x : c[k];
            }
        }
        for (int j = m; j >= 1; j--) {
            for (int k = 1; k <= c[0] && k <= j; k++) {
                int temp = dp[j - k] + b[k];
                dp[j] = temp > dp[j] ? temp : dp[j];
            }
        }
    }
    printf("%d\n", dp[m]);
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2022-03-042，如有侵权请联系 cloudcommunity@tencent.com 删除

int