建设工程网站资质人员查询,常州模板网站建设价格,怎么做关不掉的网站,西部数码网站管理系统第一题
有两只猫咪和n条不同类型的鱼#xff0c;每条鱼都只能被其中一只猫咪吃掉。 下标为i处的鱼被吃掉的得分为: 如果第一只猫咪吃掉,则得分为reward1[i]。如果第二只猫咪吃掉,则得分为reward[i]。 给你一个正整数数组reward1 #xff0c;一个正整数数组reward2#xff0…第一题
有两只猫咪和n条不同类型的鱼每条鱼都只能被其中一只猫咪吃掉。 下标为i处的鱼被吃掉的得分为: 如果第一只猫咪吃掉,则得分为reward1[i]。如果第二只猫咪吃掉,则得分为reward[i]。 给你一个正整数数组reward1 一个正整数数组reward2和一个非负整数k。 请你返回第一只猫咪恰好吃掉k条鱼的情况下最大得分为多少。 输入 1 1 3 4 4 4 1 1 2 输出 15 说明 这个例子中,第一只猫咪吃掉第2和3条鱼(下标从0于始),第二只猫咪吃掉第0和1条鱼。 总得分为443415。 15是最高得分。
思路
定义状态令 dp[i][j] 表示第一只猫咪吃掉 i 条鱼第二只猫咪吃掉 j 条鱼时能得到的最大得分。初始状态dp[0][0] 0表示两只猫咪都没有吃鱼时得分为 0。状态转移对于每一条鱼有三种选择 第一只猫咪吃掉那么 dp[i][j] dp[i-1][j] reward1[ij-1]其中 reward1[ij-1] 表示第 ij-1 条鱼的得分。第二只猫咪吃掉那么 dp[i][j] dp[i][j-1] reward2[ij-1]其中 reward2[ij-1] 表示第 ij-1 条鱼的得分。两只猫咪都不吃那么 dp[i][j] dp[i][j]不改变得分。取这三种选择中的最大值作为 dp[i][j] 的值。 最终答案由于题目要求第一只猫咪恰好吃掉 k 条鱼那么最终答案就是 dp[k][n-k]其中 n 是鱼的总数。
#include iostream
#include vector
using namespace std;int maxScore(vectorint reward1, vectorint reward2, int k) {int n reward1.size(); // 鱼的总数vectorvectorint dp(k 1, vectorint(n - k 1, 0)); // 定义状态数组for (int i 0; i k; i) { // 遍历第一只猫咪吃掉的鱼数for (int j 0; j n - k; j) { // 遍历第二只猫咪吃掉的鱼数if (i 0 j 0) continue; // 跳过初始状态int score 0; // 记录当前得分if (i 0) { // 如果第一只猫咪可以吃掉一条鱼score max(score, dp[i-1][j] reward1[ij-1]); // 更新得分}if (j 0) { // 如果第二只猫咪可以吃掉一条鱼score max(score, dp[i][j-1] reward2[ij-1]); // 更新得分}dp[i][j] score; // 更新状态数组}}return dp[k][n-k]; // 返回最终答案
}int main() {vectorint reward1 {1, 1, 3, 4}; // 输入第一只猫咪的得分数组vectorint reward2 {4, 4, 1, 1}; // 输入第二只猫咪的得分数组int k 2; // 输入第一只猫咪要吃掉的鱼数cout maxScore(reward1, reward2, k) endl; // 输出最大得分return 0;
}第二题
在一个城市探险活动中,主办方标记了n个地标,编号为0到n-1。大壮需要从城市的起点(编号为0的地标)经过一系列地标后,最终到达终点(编号为n-1的地标)。每个地标都对应一个整数,表示从当前地标可以跳过的地标数量。例如,如果小王当前处于编号为i的地标,且地标对于的数字为nums[i],那么他可以选择跳过中间所有地标,而是直接去往任意编号为i用j的地标,其中0j nums[i]且ijn。主办方确保有路线可以成功到达终点地标,为了顺利到达终点,请帮助大壮计算,他需要经过的最少的地标数量。
输入描述 地标组数 输出描述 经过最少地标数量
示例1 输入 [2, 1, 1,3, 1, 3, 1, 4] 输出 4
示例2 输入 [5, 4, 3, 2, 1,2, 3, 1, 1, 2] 输出 3
思路
定义一个变量 ans 表示经过的地标数量初始为 0。定义一个变量 cur 表示当前所在的地标编号初始为 0。定义一个变量 next 表示下一步要跳到的地标编号初始为 0。使用一个 while 循环当 cur n - 1 时执行以下操作 遍历从 cur 1 到 cur nums[cur] 的所有地标编号 i找出使得 i nums[i] 最大的那个 i并赋值给 next。如果 next cur说明无法继续前进返回 -1 表示无解。否则将 cur 更新为 next并将 ans 加一。 返回 ans 作为最终答案。
根据以上思路可以用 C 语言编写如下代码
#include iostream
#include vector
using namespace std;int minLandmarks(vectorint nums) {int n nums.size(); // 地标的总数int ans 0; // 经过的地标数量int cur 0; // 当前所在的地标编号int next 0; // 下一步要跳到的地标编号while (cur n - 1) { // 当没有到达终点时int max_jump 0; // 记录能跳到的最远距离for (int i cur 1; i cur nums[cur]; i) { // 遍历所有可选的地标if (i nums[i] max_jump) { // 如果能跳得更远max_jump i nums[i]; // 更新最远距离next i; // 更新下一步目标}}if (next cur) return -1; // 如果无法前进返回-1表示无解cur next; // 更新当前位置ans; // 更新经过的地标数量}return ans; // 返回最终答案
}int main() {vectorint nums {2, 1, 1, 3, 1, 3, 1, 4}; // 输入地标组数cout minLandmarks(nums) endl; // 输出经过最少地标数量return 0;
}
