Huster水仙

题解

/ 注册

全部文章 / 题解（共104篇）

题解 | #坠落的蚂蚁#

模拟思维详细思路参考高赞题解，图片一目了然要点：两只蚂蚁碰头可理解为互不干扰，各走各的左边向左的、右边向右的蚂蚁对A没有影响左边向右的、右边向左的蚂蚁可以两两抵消最终取决于抵消后，最靠近A的蚂蚁的运动时间代码思路：按位置排序、找到A的下标，分别统计左边向右、右边向左蚂蚁、输出 #i...

C++

2023-02-14

0 541

题解 | #环形链表的约瑟夫问题(进阶)#

约瑟夫问题递推法模拟的时间开销太大不得不回头考虑递推关系：将编号改为从0开始,记f(n,m)为原问题的解由于第一次遍历了0~(m-1)%n，则第二次遍历相当于将整个队伍循环左移了k位(k=m%n) 所以子问题f(n-1,m)的解循环右移k位即为原问题的解f(n,m) f(n,...

C++

2023-02-13

2 471

题解 | #路径打印#

字符串分拆排序比较相邻路径相同层数输出 #include<iostream> #include<algorithm> #include<string> #include<cstring> #include<vector> using...

C++

2023-02-13

1 489

题解 | #整数拆分#

完全背包变形（参考高赞回答）第i轮 dp[j]:前i种物品组合成容量恰好为j的方法数递推关系：类比完全背包（优化） dp[j]=dp[j]+dp[j-w[i]] #include<iostream> #include<cmath> using namespace s...

C++

2023-02-13

1 428

题解 | #放苹果#

DP：M个物品划分成N份关键：比较盘子和苹果的个数大小 dp[i][j]：i个苹果分给j个盘子 ①盘子比苹果多：一定有盘子是空的，摔掉多余空盘子即可： dp[i][j]=dp[i][i] ②盘子不比苹果多: 要么每个盘子都非空，相当于先给每个盘子放一个苹果，只用考虑剩下的i-j个苹果：dp[i-...

C++

2023-02-12

8 620

题解 | #最小邮票数#

0-1背包变形：容量恰好用完类比：容量：给定的总面值sum、邮票[i]的重量：面值w[i] 、价值：均为1 第i轮 dp[j]：前i张邮票凑出总面值为j的最少张数初始状态：dp[0]=0; dp[i]=INF(0<i<=sum) 表示无法完成递推关系：dp[j]=min(dp...

C++

2023-02-11

0 347

题解 | #多重背包#

多重背包每种物品有若干个,物品i的体积：w[i]、价值：v[i]、数量：amount 第i轮：dp[j]:前i个物品装进容量为j的背包所获得的最大价值采用二进制将同种物品组合成新的物品，化为0-1背包求解 #include<iostream> #include<string&...

C++

2023-02-11

0 492

题解 | #点菜问题#

0-1背包每种物品只有一个,物品i的体积：w[i]、价值：v[i] dp[i][j]:前i个物品装进容量为j的背包所获得的最大价值 ① 不放第i个物品 dp[i][j]=dp[i-1][j] ② 放入第i个物品 dp[i][j]=dp[i-1][j-w[i]]+v[i] #include<...

C++

2023-02-11

0 528

题解 | #最长公共子序列#

最长公共子序列：DP 思路：s1[i]与s2[j]是否匹配，dp[i+1][j+1]:以s[i]与s[j]为末尾匹配的最长公共序列长度，由于要输出序列，所以得到公共子序列长度后，需要从后往前拼接 ①是：dp[i+1][j+1]=dp[i][j]+1;都往前一个字符，再匹配 ②否：dp[i+1][...

C++

2023-02-10

1 515

题解 | #合唱队形#

最长“山顶”子序列 DP：分别递推以s[i]开头的最长下降子序列、以s[i]结尾的最长上升子序列 #include<iostream> #include<cstring> using namespace std; const int maxn=101; int s[max...

C++

2023-02-10

0 440