当前位置：首页 > article >正文

力扣10.1

article 2024/10/2 2:56:38

983. 最低票价

在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。

火车票有三种不同的销售方式：

一张为期一天的通行证售价为 $cos t s [0]$ 美元；
一张为期七天的通行证售价为 $cos t s [1]$ 美元；
一张为期三十天的通行证售价为 $cos t s [2]$ 美元。
通行证允许数天无限制的旅行。例如，如果我们在第 2 天获得一张为期 7 天的通行证，那么我们可以连着旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。

返回你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费。

数据范围

1 <= days.length <= 365
1 <= days[i] <= 365
days 按顺序严格递增
costs.length == 3
1 <= costs[i] <= 1000

分析

令dp[i]表示第i天所需的最小花费，用st数组记录第i天是否需要旅游，状态转移如下：

$if\ vis[i]\ dp[i]=min(dp[max(0,i-1/7/30)]+val[1/7/30]$ ，这里若i不足1/7/30天，可以从第0天直接开始买
$\ dp[i]=dp[i-1]$

代码

class Solution {
public:
    const static int N = 400;
    int dp[N];
    bool st[N];
    int dt[4] = {1, 7, 30};
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        int n = days.size();
        for(int i = 0; i < n; i ++ ) st[days[i]] = true;
        memset(dp, 0x3f, sizeof(dp));
        dp[0] = 0;
        for(int i = 1; i <= 365; i ++ ) {
            if(st[i]) {
                for(int j = 0; j < 3; j ++ ) {
                    dp[i] = min(dp[max(0, i - dt[j])] + costs[j], dp[i]);
                }
            } else dp[i] = dp[i - 1];
        }
        return dp[365]; 
    }
};

2321. 拼接数组的最大分数

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，长度都是 n 。

你可以选择两个整数 left 和 right ，其中 0 <= left <= right < n ，接着交换两个子数组 nums1[left...right] 和 nums2[left...right] 。

例如，设 nums1 = [1,2,3,4,5] 和 nums2 = [11,12,13,14,15] ，整数选择 left = 1 和 right = 2，那么 nums1 会变为 [1,12,13,4,5] 而 nums2 会变为 [11,2,3,14,15] 。
你可以选择执行上述操作一次或不执行任何操作。

数组的分数取 sum(nums1) 和 sum(nums2) 中的最大值，其中 sum(arr) 是数组 arr 中所有元素之和。

返回可能的最大分数。

子数组是数组中连续的一个元素序列。arr[left...right] 表示子数组包含 nums 中下标left 和 right 之间的元素（含下标 left 和 right 对应元素）。

数据范围

n == nums1.length == nums2.length
1 <= n <= 105
1 <= nums1[i], nums2[i] <= 104

分析

本质是子数组最大和，构建一个新数组，值为nums1和nums2的差，此时只需要找最大子数组t1和和最小子数组和t2，令nums1的和为sum1，nums2的和为sum2，则答案就是max(sum1-t2,sum2+t1)

代码

class Solution {
public:
    const static int N = 1e5 + 5;
    int dp1[N], dp2[N];
    int nums[N];
    int maximumsSplicedArray(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int sum1 = 0, sum2 = 0;
        int d1 = 0, d2 = 0;
        for(int i = 0; i < n; i ++ ) {
            nums[i + 1] = nums1[i] - nums2[i];
            sum1 += nums1[i];
            sum2 += nums2[i];
        }
        for(int i = 1; i <= n; i ++ ) cout << nums[i] << " ";
        cout << endl;
        dp1[0] = 0;
        dp2[0] = 0;
        for(int i = 1; i <= n; i ++ ) {
            dp1[i] = max(0, dp1[i - 1] + nums[i]);
            dp2[i] = min(0, dp2[i - 1] + nums[i]);
            d1 = max(d1, dp1[i]);
            d2 = min(d2, dp2[i]);
        }
        return max(sum1 - d2, sum2 + d1);
    }
};

LCR 166. 珠宝的最高价值

现有一个记作二维矩阵 frame 的珠宝架，其中frame[i][j]为该位置珠宝的价值。拿取珠宝的规则为：

只能从架子的左上角开始拿珠宝
每次可以移动到右侧或下侧的相邻位置
到达珠宝架子的右下角时，停止拿取
注意：珠宝的价值都是大于 0 的。除非这个架子上没有任何珠宝，比如 frame = [[0]]。

数据范围

0 < frame.length <= 200
0 < frame[0].length <= 200

分析

状态转移：

$d p [i] [j] = ma x (d p [i] [j - 1], d p [i - 1] [j]) + v$
主要讲一下空间压缩，对于dp[i],只用到了dp[i-1]的数据，计算完后dp[i-1]，因此可以将dp[i]的数据存到dp[i-1]的地方，再想一下其实两个数组就够了，只需要下标对2取模，dp[i]的值存到dp[i%2]的位置，使用dp[i-1]的值就是使用dp[(i-1)%2]的值

代码

class Solution {
public:
    const static int N = 205;
    int dp[2][N];
    int jewelleryValue(vector<vector<int>>& frame) {
        int n = frame.size(), m = frame[0].size();
        for(int i = 1; i <= n; i ++ ) {
            for(int j = 1; j <= m; j ++ ) {
                dp[i % 2][j] = max(dp[(i - 1) % 2][j], dp[i % 2][j - 1]) + frame[i - 1][j - 1];
            }
        }
        return dp[n % 2][m];
    }
};