先看题目：https://ac.nowcoder.com/acm/problem/51170题目描述：N堆石子排成一排，每次可以合并相邻的两堆，每次合并得分为合并的两堆石子之和，问把所有石子合成一堆的最小得分是多少？解题思路：区间dp入门题，dp[i][j]表示从i到j合并的最小得分，则可写出状态转移方程： dp[i][j] = min( dp[i][j], dp[i][k]+dp[k+1][j]+sum(i,j) )注：1.由于要求最小得分，dp初始化为inf，2.由转移方程可以看出，要求(i,j)这个区间需要比它区间长度小的那些区间的状态。故for循环第一层枚举长度，第二层枚举区间起点，则...

先看题目：https://ac.nowcoder.com/acm/contest/5723/B题目描述：有一些草堆块放在一些格子里，每个格子只能放一个草堆块，这些草堆块会形成一个连通块，算连通块的外围周长。解题思路：我一开始的思路是，每个初始ans是4*N，也就是每个草堆块四个面的周长都算的情况，然后跟据每个草堆块是向外还是向内可以发现每个草堆块朝向连通块内部的边可以去掉。比如，对于某个草堆块能找到一个草堆块与它y相同，但是x比它大，那么就不必加上这个草堆块的朝右的那个边的长度。但实际上一个简单的反例就可以说明这个思想是错误的。 反例：  后来师哥给出了dfs的解法，令我再次感叹自己的弱小。正...

先看题目：https://ac.nowcoder.com/acm/problem/17193题目描述：略解题思路：暴力枚举总共有100^100次方种情况，考虑使用dp。那么状态定义为什么呢？如果定义为dp[i][j]表示前i项有没有构成j这个数字，那么状态转移方程就变得很麻烦了，首先，开个1e8的数组就很大了，其次，每次要添一个数都需要for循环一遍，很麻烦，空间时间复杂度都很高。bitset在解决这类问题上就很好用！ 定义： bitset<MAX> dp[101]; //dp[i]表示前i项构成了哪些数字，比如前i项能构成16，那么第16位就为1状态转移也很好写，依题意，需累加第...

先看题目：https://ac.nowcoder.com/acm/contest/5723/J题目描述：给出一些边长都为k的正方形的中心坐标，如果只有一对正方形重叠，则输出重叠面积，如果有多对正方形重叠，输出-1，如果没有正方形重叠，则输出0解题思路：画图模拟一下可知，如果两正方形中点坐标为(x1,y1)和(x2,y2)，若|x1-x2| < k && |y1-y2| < k时，才能重叠，其重叠形成的矩形的面积为(k-|y1-y2|)*(k-|x1-x2|)这道题普通n^2搜索是显然过不了的，但是可以思考思考做出优化。这道题的n^2搜索 for(int i = 1;...

先看题目：https://ac.nowcoder.com/acm/problem/207754题目描述：牛牛参观景点，任意两个景点间都有路相连，牛牛希望经过某些路，为了参观完所有景点并且每个景点只参观一次，有多少种方法？解题思路：显然，如果A-B,B-C,C-A都要走即A、B、C成环了，那么A必然要经过两次，显然不行。这道题怎么考虑呢？举个例子试试：如图，(1,2)要走，(4,5)要走，(6,7)要走，(7,8)要走，(7,9)要走发现，如果某个点的度大于2，显然也是不行的，比如7无论如何都会经过2次如果(7,9)这条边不存在，还是从1-9，我们来思考下总共有多少种方法？把每个集合看成一个整体...

转载：https://blog.csdn.net/xyt8023y/article/details/46312499并查集来判断是否有环路。首先初始化所有元素的根为-1，-1代表根节点，接下来对于图中的每一条边(v1,v2)都并入集合，并入的方式为查找v1和v2的根节点，然后让v2的根节点作为v1的根节点，查找根节点的过程为：如果当前的结点根为-1，说明这个结点就是根，直接返回，否则再继续查找结点父亲的根，直到找到祖先结点。 int findroot(int x) { return fa[x] == -1 ? x : fa[x]=findroot(fa[x]); }找到v1的根root1和v2...

转载：https://www.acwing.com/blog/content/31/二分模板一共有两个，分别适用于不同情况算法思路：假设目标值在闭区间[l, r]中， 每次将区间长度缩小一半，当l = r时，我们就找到了目标值。版本1当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时，其更新操作是r = mid或者l = mid + 1;，计算mid时不需要加1。 C++ 代码模板： int bsearch_1(int l, int r) { while (l < r) { int mid = l + r >> 1; if (check(mid)) r...

英语好就先看题目：https://ac.nowcoder.com/acm/contest/5723/A题目描述；FJ有块农田太崎岖了，他要买一辆新拖拉机才能在这里巡视。这块农田由N x N个格子的非负整数表示高度(1<=N<=500)。拖拉机从当前格子走到相邻格子（东、南、西、北四个方向）的代价为高度差D，则FJ驶过这两个格子的拖拉机最少也要值D块钱。 FJ愿意花足够的钱买一辆新的拖拉机使得他能以最小的高度差走遍所有格子的一半(如果格子总数是奇数，那么一半的值为四舍五入的值)。因为FJ很懒，所以他找到你帮他编程计算他最小需要花多少钱买到符合这些要求的拖拉机解题思路：由于小的价值若能...

先看题目：https://ac.nowcoder.com/acm/contest/5968/C题目描述：n个人通过小船渡河，小船每次只能运两人，渡河时间等于两人渡河最慢的那个的时间，(小船要考虑有人划回来),问最少花费多长时间能够把n个人送到对岸？解题思路：先考虑范围小一点的时候，n==1，n==2都很显然，n==3也比较显然，1当渡夫，把2，3挨个送到对岸，当n==4的时候就有点麻烦了，n==4时，可以1当渡夫把2，3，4挨个接过去，这样的话时间是：t[2]+t[1]+t[3]+t[1]+t[4], 然而还有一种方法，也有可能成为答案，思想就是尝试把t[3]弄掉，可以让1，2先划过去，然后1...

先看题目：https://ac.nowcoder.com/acm/contest/5968/A题目描述：有n级台阶，在i级台阶可以走到i+1级台阶(仅h[i+1] == h[i]+1)时，也可以往下一级台阶到i-1级。如果连续下降k级台阶到达了第i级台阶可以上升到高度小于等于h[i]+2^k的任何一个位置。解题思路：定义状态f[i]为到达i级台阶的最小步数，枚举i,j,代表从某个台阶向下k级到达j级，k可以由ceil(log2(a[i]-a[j]))来求出，如果j+k < i，那么可以更新f[i]。为什么不再去考虑是向下走k+1级，k+2级...到达j的呢？这是因为f[i]一定是非递减的...

先看题目：https://ac.nowcoder.com/acm/contest/5968/E题目描述：n个物品中挑选m个物品，任意两个物品的位置差大于等于k，求最大受欢迎度。解题思路：背包问题，让求n个物品中挑m个物品的最大受欢迎度，跟据题意，设f[i][j]是前i个物品挑选j个的最大受欢迎度，转移方程：f[i][j] = max{f[i-1][j], f[i-k][j-1]+a[i]}这道题在编程实现上有很多需要注意与理解的地方：1.由于欢迎度可以是负数，因此，dp[][]应当初始化为负无穷。2.由于1，因此跟据状态转移方程的写法，无法通过dp[0][]一步步转移得来，因此需要初始化dp[...

先看题目：https://ac.nowcoder.com/acm/problem/53675题目描述：给出一个m*n的地图，标0的可以走，标1的不能走。问从(m,1)点开始走到(1,n)点有多少条路径？ 解题思路：与过河卒那题一样的解法，这里就不再多说了。不同之处在于枚举方向跟据题意需要变化。数据量比较多要用快速读入。 代码： #include<bits/stdc++.h> using namespace std; int mp[3010][3010]; int dp[3010][3010]; template<class T>inline void read(T &a...

先看题目：https://ac.nowcoder.com/acm/problem/16810题目描述：有一个导弹系统，每一发炮弹都不能高于前一发的高度。第一问是问能拦截多少导弹？第二问是问要拦截所有导弹最少需要多少套这样的导弹系统？解题思路：第一问就是求序列的最长不上升子序列。第二问我的思路是：整个序列中递增的那些数肯定是被不同的导弹系统拦截，那么求出最长上升子序列的长度就完了呗，这里稍严谨点，引入Dilworth定理。Dilworth定理说了什么一件事呢？一个数列划分成最少的不升子序列的数目就等于这个数列的最长上升子序列的长度 不上升子序列就是导弹系统。要拦截所有导弹最少需要多少套这样的导弹...

先看题目：https://ac.nowcoder.com/acm/problem/16708题目描述：小卒从(0,0)点出发，不能通过象的控制点，问小卒到达(n,m)的路径有几条？解题思路：dp[i][j]定义为从(0,0)到(i,j)的路径数,dp[i][j]=dp[i-1][j]+dp[i][j-1]这题处理边界稍有点麻烦。编程实现的话用for循环就能解决。结果可能会比较大，要开long long代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; int n, m, x, y; ll dp...