写了两个小时的说，思路和状态转移方程不难想，但是代码调试了好久。刚开始想用三维dp，后来发现自己把自己绕进去了，二维足够(滚动数组应该也可以进一步优化到一维。） 考查：贪心，前缀和，线性dp 状态表示：dp[i][j] 表示第i天，手里有j个糖果时花费的最少费用，因为每天至少吃一个，贪心的想法，每天就吃一个，所以j大于等于1，答案即为dp[n][1]。 转移方程：设第i天买了k个糖果，则  dp[i][j]=min(dp[i][j],dp[i-1][j-k+1]+val[i][k]+k*k);  就是把第i天拥有的j个糖果分成两部分，一部分来自k，另一部分来自i-1天剩下的，所以是j-k+1。...

题目：链接：https://ac.nowcoder.com/acm/contest/24213/1014 来源：牛客网 求方法个数，时间给了1s于是不得不放弃暴力的想法（qaq)那就dp！ 先想总的方法数：显然是4的n次方，那么我们就在找一下不会亏本的方法数，求一下gcd，输出答案就好了。 状态表示：我的状态表示比较麻烦（写完之后看了别的佬的代码）用了三维。 dp[i][j][k],i表示买了i张，j为当前这张的中奖金额，k为盈利了多少，dp[i][j][k]为方法数。 状态计算：显然每张彩票都要用上，所以只能由前一张彩票转移而来，那前一张的盈利数额应该为k-（j-3）即当前盈利数额减去这张的...

看到这个题先想到的是st表，后来发现用st表写内存超限了，才去想dp（还参考了别人的代码，我是dp弱子） st表的思路：（随便看看）求当前这个数字往后推k个的和，然后把这个值用数组存起来，暴力走一遍所有元素，ans=当前元素的值加上之后的元素中的最大值，于是想到最大值可以用st表维护，上代码（ac百分之50） 佬也可以浇浇窝怎么优化内存 #include<bits/stdc++.h> using namespace std; #define lowbit(x) ((x)&-x) typedef long long ll; typedef long double ld; ty...

1010 【木】迷雾森林 看别人都在写递推，我就写个记忆化搜索吧，因为比较简单，所以直接上代码（） 需要注意的是，给dis赋值为-INF做初始值时，会出问题，大家可以自己试试 #include<bits/stdc++.h> using namespace std; #define lowbit(x) ((x)&-x) typedef long long ll; typedef long double ld; typedef unsigned long long ull; const ll INF = 0x3f3f3f3f3f3f3f3fLL; int m,n; const ...

看各位大佬都是用字典树写的c题,我来斗胆分享一下我的字符串哈希做法（其实是不会字典树，明天就去学了，补药压力我）先说想法：先假设最后的状态是空白的，就是打完全部删除，那每个字符串除了从开头开始可以蹭别的字符串的部分以外，只需要加上 剩下的部分乘以2次（一次打出，一次删除）。然后再考虑其实不用全部删除，最后可以留下一个字符串，那当然留下最长的一个可以使得操作次数最少。用set记录已经出现过的前缀，于是就有了我的写法（大佬们随便看看就是我的荣幸了）