各大网站投放广告怎么做,拼多多一件代发货源app,热门视频素材,教育培训类网站设计983. 最低票价
在一个火车旅行很受欢迎的国度#xff0c;你提前一年计划了一些火车旅行。在接下来的一年里#xff0c;你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。
火车票有 三种不同的销售方式 #xff1a;
一张 为期一天 的通行证售…983. 最低票价
在一个火车旅行很受欢迎的国度你提前一年计划了一些火车旅行。在接下来的一年里你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。
火车票有 三种不同的销售方式
一张 为期一天 的通行证售价为 c o s t s [ 0 ] costs[0] costs[0] 美元一张 为期七天 的通行证售价为 c o s t s [ 1 ] costs[1] costs[1] 美元一张 为期三十天 的通行证售价为 c o s t s [ 2 ] costs[2] costs[2] 美元。 通行证允许数天无限制的旅行。 例如如果我们在第 2 天获得一张 为期 7 天 的通行证那么我们可以连着旅行 7 天第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。
返回 你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费 。
数据范围
1 days.length 3651 days[i] 365days 按顺序严格递增costs.length 31 costs[i] 1000
分析
令dp[i]表示第i天所需的最小花费用st数组记录第i天是否需要旅游状态转移如下 i f v i s [ i ] d p [ i ] m i n ( d p [ m a x ( 0 , i − 1 / 7 / 30 ) ] v a l [ 1 / 7 / 30 ] if\ vis[i]\ dp[i]min(dp[max(0,i-1/7/30)]val[1/7/30] if vis[i] dp[i]min(dp[max(0,i−1/7/30)]val[1/7/30]这里若i不足1/7/30天可以从第0天直接开始买 e l s e d p [ i ] d p [ i − 1 ] else \ dp[i]dp[i-1] else 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(vectorint days, vectorint 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.length1 n 1051 nums1[i], nums2[i] 104
分析
本质是子数组最大和构建一个新数组值为nums1和nums2的差此时只需要找最大子数组t1和和最小子数组和t2令nums1的和为sum1nums2的和为sum2则答案就是max(sum1-t2,sum2t1)
代码
class Solution {
public:const static int N 1e5 5;int dp1[N], dp2[N];int nums[N];int maximumsSplicedArray(vectorint nums1, vectorint 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 2000 frame[0].length 200
分析
状态转移 d p [ i ] [ j ] m a x ( d p [ i ] [ j − 1 ] , d p [ i − 1 ] [ j ] ) v dp[i][j]max(dp[i][j-1],dp[i-1][j])v dp[i][j]max(dp[i][j−1],dp[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(vectorvectorint 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];}
};
