红鲤鱼与绿鲤鱼与驴 残血回归 之前递归一直没学好，感觉总是绕不过那个弯，所以就一直不敢碰DFS，今天终于鼓起勇气，看遍了n多视频和文章后，好像有点感觉了 深度优先搜索 DFS ：沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。 伪代码： void dfs(状态A){ if(A不合法) return ; if(A为目标状态) 输出 if(A不为目标状态) dfs(A+*) //递...

红鲤鱼与绿鲤鱼与驴 今天把昨天学的二分和快速幂的练习做了一下 洛谷P2440 木材加工:https://www.luogu.com.cn/problem/P2440 1、题意：n块木头切成等长的k段，求小段木头最长可以为多少。 2、思路：比较基础 正常做就行 3、代码： #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> using namespace std; long long n,k; long long a[100005]; int jud...

红鲤鱼与绿鲤鱼与驴 今天学习 二分法 and 快速幂 二分查找函数：在一个升序数组的 begin 和 end 前闭后开区间内进行二分查找lower_bound (begin,end,val) 返回大于或等于val的第一个元素位置upper_bound (begin,end,val) 返回大于val的第一个元素位置如果所有元素都小于 val 则返回 end 的位置补充：头文件：algorithm 如果要二分的是个小数 需要规定精度 double left,right,mid; while(right - left > eps ){ mid = (right + left) / 2;...

红鲤鱼与绿鲤鱼与驴 今天把昨天学的背包问题的练习做了一下 AcWing278 数组组合https://ac.nowcoder.com/acm/contest/1042/A 1、题意：在N个数中找出其和为M的若干个数。先读入正整数N（1<N<100）和M(1<M<10000)， 再读入N个正数（可以有相同的数字，每个数字均在1000以内），在这N个数中找出若干个数， 使它们的和是M，把满足条件的数字组合都找出来以统计组合的个数，输出组合的个数（不考虑组合是否相同）。 2、思路：典型的01背包问题，n个整数看作n个物品，m看作背包容量，在外层循环到i时，设f[j]表示...

前几天过分沉迷于沙发和电视剧 突然被叫醒 队友已经在前进了所以今天我也要开始我的 “快乐暑假” 了 清醒一下脑子 调整一下状态 今天从好奇了很久的 DP 开始： 动态规划 DP：状态和转移。 经典例题：最长上升子序列 LIS状态：f [ i ] 表示以 i 结尾的上升子序列中的最长长度。#include<iostream> #include<cmath> #include<algorithm> using namespace std; int a[55],f[55]; int main(){ int n; cin>>n; for(i...