2739. 总行驶距离
卡车有两个油箱。给你两个整数，mainTank 表示主油箱中的燃料（以升为单位），additionalTank 表示副油箱中的燃料（以升为单位）。
该卡车每耗费 1 升燃料都可以行驶 10 km。每当主油箱使用了 5 升燃料时，如果副油箱至少有 1 升燃料，则会将 1 升燃料从副油箱转移到主油箱。
返回卡车可以行驶的最大距离。
注意：从副油箱向主油箱注入燃料不是连续行为。这一事件会在每消耗 5 升燃料时突然且立即发生。
示例 1：
输入：mainTank = 5, additionalTank = 10
输出：60
解释：
在用掉 5 升燃料后，主油箱中燃料还剩下 (5 - 5 + 1) = 1 升，行驶距离为 50km 。
在用掉剩下的 1 升燃料后，没有新的燃料注入到主油箱中，主油箱变为空。
总行驶距离为 60km 。
示例 2：
输入：mainTank = 1, additionalTank = 2
输出：10
解释：
在用掉 1 升燃料后，主油箱变为空。
总行驶距离为 10km 。
提示：
1 <= mainTank, additionalTank <= 100解答：数据量比较小，直接按照题意一次次模拟
class Solution {
public int distanceTraveled(int mainTank, int additionalTank) {
int ans = 0;
while (mainTank >= 5) {
ans += 50;
mainTank -= 5;
if (additionalTank > 0) {
additionalTank--;
mainTank++;
}
}
return ans + mainTank * 10;
}
}2740. 找出分区值
给你一个 正 整数数组 nums 。
将 nums 分成两个数组：nums1 和 nums2 ，并满足下述条件：
数组 nums 中的每个元素都属于数组 nums1 或数组 nums2 。
两个数组都 非空 。
分区值 最小 。
分区值的计算方法是 |max(nums1) - min(nums2)| 。
其中，max(nums1) 表示数组 nums1 中的最大元素，min(nums2) 表示数组 nums2 中的最小元素。
返回表示分区值的整数。
示例 1：
输入：nums = [1,3,2,4]
输出：1
解释：可以将数组 nums 分成 nums1 = [1,2] 和 nums2 = [3,4] 。
- 数组 nums1 的最大值等于 2 。
- 数组 nums2 的最小值等于 3 。
分区值等于 |2 - 3| = 1 。
可以证明 1 是所有分区方案的最小值。
示例 2：
输入：nums = [100,1,10]
输出：9
解释：可以将数组 nums 分成 nums1 = [10] 和 nums2 = [100,1] 。
- 数组 nums1 的最大值等于 10 。
- 数组 nums2 的最小值等于 1 。
分区值等于 |10 - 1| = 9 。
可以证明 9 是所有分区方案的最小值。
提示：
2 <= nums.length <= 10^5
1 <= nums[i] <= 10^9解答：排序，取相邻两个元素的最小差值
class Solution {
public int findValueOfPartition(int[] nums) {
Arrays.sort(nums);
int res=Integer.MAX_VALUE;
int n=nums.length;
for(int i=1;i<n;i++)res=Math.min(nums[i]-nums[i-1],res);
return res;
}
}
2741. 特别的排列
给你一个下标从 0 开始的整数数组 nums ，它包含 n 个 互不相同 的正整数。如果 nums 的一个排列满足以下条件，我们称它是一个特别的排列：
对于 0 <= i < n - 1 的下标 i ，要么 nums[i] % nums[i+1] == 0 ，要么 nums[i+1] % nums[i] == 0 。
请你返回特别排列的总数目，由于答案可能很大，请将它对 109 + 7 取余 后返回。
示例 1：
输入：nums = [2,3,6]
输出：2
解释：[3,6,2] 和 [2,6,3] 是 nums 两个特别的排列。
示例 2：
输入：nums = [1,4,3]
输出：2
解释：[3,1,4] 和 [4,1,3] 是 nums 两个特别的排列。
提示：
2 <= nums.length <= 14
1 <= nums[i] <= 10^9解答：状态压缩dp解法
class Solution {
private int MOD = (int) 1e9 + 7;
public int specialPerm(int[] nums) {
var n = nums.length;
var f = new int[1 << n][n];
for (int i = 0; i < n; ++ i) f[0][i] = 1;
for (int i = 0; i < 1 << n; ++ i) {
for (int j = 0; j < n; ++ j) {
for (int k = 0; k < n; ++ k) {
if (((i >> k) & 1) == 1 && (nums[j] % nums[k] == 0 || nums[k] % nums[j] == 0)) {
f[i][j] = (f[i][j] + f[i ^ (1 << k)][k]) % MOD;
}
}
}
}
int ans = 0;
for (int i = 0; i < n; ++ i) ans = (ans + f[((1 << n) - 1) ^ (1 << i)][i]) % MOD;
return ans;
}
}2742. 给墙壁刷油漆
给你两个长度为 n 下标从 0 开始的整数数组 cost 和 time ，分别表示给 n 堵不同的墙刷油漆需要的开销和时间。你有两名油漆匠：
一位需要 付费 的油漆匠，刷第 i 堵墙需要花费 time[i] 单位的时间，开销为 cost[i] 单位的钱。
一位 免费 的油漆匠，刷 任意 一堵墙的时间为 1 单位，开销为 0 。但是必须在付费油漆匠 工作 时，免费油漆匠才会工作。
请你返回刷完 n 堵墙最少开销为多少。
示例 1：
输入：cost = [1,2,3,2], time = [1,2,3,2]
输出：3
解释：下标为 0 和 1 的墙由付费油漆匠来刷，需要 3 单位时间。同时，免费油漆匠刷下标为 2 和 3 的墙，需要 2 单位时间，开销为 0 。总开销为 1 + 2 = 3 。
示例 2：
输入：cost = [2,3,4,2], time = [1,1,1,1]
输出：4
解释：下标为 0 和 3 的墙由付费油漆匠来刷，需要 2 单位时间。同时，免费油漆匠刷下标为 1 和 2 的墙，需要 2 单位时间，开销为 0 。总开销为 2 + 2 = 4 。
提示：
1 <= cost.length <= 500
cost.length == time.length
1 <= cost[i] <= 10^6
1 <= time[i] <= 500解答：使用0/1背包求解
class Solution {
int n;
int[][] memo;
int[] cost, time;
public int paintWalls(int[] cost, int[] time) {
this.n = cost.length;
this.cost = cost;
this.time = time;
this.memo = new int[n][2 * n + 1];// 免费时长可以为负数，因此需要加偏移量
for (int i = 0; i < n; i++){
Arrays.fill(memo[i], -1);
}
return dfs(n - 1, n);// 偏移量防止负数
}
// 免费时长为j，刷前i片墙需要的最小花费
public int dfs(int i, int j){
if (i < j - n) return 0;// 剩余所有墙都可以由免费油漆工刷
if (i < 0) return 0x3f3f3f3f;
if (memo[i][j] != -1) return memo[i][j];
// 免费油漆工刷
int res = dfs(i - 1, j - 1);
// 付费油漆工刷
res = Math.min(res, dfs(i - 1, j + time[i]) + cost[i]);
return memo[i][j] = res;
}
}
