cefegent

题解

/ 注册

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

题解 | #牛牛的旅游纪念品#

感觉是道比较简单的dp,但意外的比较容易做错，主要是细节很容易错。状态表示：dp[i][j]来表示从前i个物品中取到j个能得到的最大受欢迎程度。状态转移：对于第i个物品只有拿或者不拿两种选择，因为j我们保证一定能取这么多，所以如果拿第i个物品的话： dp[i][j]=dp[i-k][j-1]+a...

2025-02-12

0 44

题解 | #1015-购物#

写了两个小时的说，思路和状态转移方程不难想，但是代码调试了好久。刚开始想用三维dp，后来发现自己把自己绕进去了，二维足够(滚动数组应该也可以进一步优化到一维。）考查：贪心，前缀和，线性dp 状态表示：dp[i][j] 表示第i天，手里有j个糖果时花费的最少费用，因为每天至少吃一个，贪心的想法，每天...

2025-02-02

0 44

题解 | #小A买彩票#

题目：链接：https://ac.nowcoder.com/acm/contest/24213/1014 来源：牛客网求方法个数，时间给了1s于是不得不放弃暴力的想法（qaq)那就dp！先想总的方法数：显然是4的n次方，那么我们就在找一下不会亏本的方法数，求一下gcd，输出答案就好了。状态表示...

2025-01-31

0 41

题解 | #数学考试#

看到这个题先想到的是st表，后来发现用st表写内存超限了，才去想dp（还参考了别人的代码，我是dp弱子） st表的思路：（随便看看）求当前这个数字往后推k个的和，然后把这个值用数组存起来，暴力走一遍所有元素，ans=当前元素的值加上之后的元素中的最大值，于是想到最大值可以用st表维护，上代码（ac百...

2025-01-31

0 33

题解 | #迷雾森林#

1010 【木】迷雾森林看别人都在写递推，我就写个记忆化搜索吧，因为比较简单，所以直接上代码（）需要注意的是，给dis赋值为-INF做初始值时，会出问题，大家可以自己试试 #include<bits/stdc++.h> using namespace std; #define low...

2025-01-31

0 40