二叉树？？树状dp？？NONONO！！！   本题的树不固定，他要求去找出来一个最优的树，所以不适合使用树状dp去进行求解。但又因为题中所给的有中序遍历的序列，中序遍历序列最大的特点在于定根可将区间分成左右子树。   那么分成两部分之后就可以分别去计算这两部分，也就是在这两小部分里面取找根。 那么可以得到dp[i][j]为i,j这个区间组成的树的最高加分。 得到状态转移方程为：dp[i][j] = max(dp[i][k], dp[k+1][j])。 对于前序遍历：在每一个区间树遍历最高加分的时候去记录最优的那个根。然后重新dfs遍历得到就行。 //题目中所给的是一个中序遍历的序列，那么只要定...

在树上进行操作的记忆化搜索，通过DFS加灵活换根的方式进行。   首先先走一遍DFS，得到每个节点下的深度和，节点的个数和（包括节点自身）。   然后让1成为根，那么再进行DFS下去的每一个节点都可以有一个动态规划递推式来快速计算得到加入某个节点为根的时候的深度和。   递推式为：dp[x] = dp[fa] - num[x] + n - num[x]。   其实某个节点作为根的深度和就等于上一个节点作为根的深度和加上因为根的改变而距离增大的节点数目以及减去因为根改变而距离减少而节点数目。   #include <bits/stdc++.h> using nam...

很折磨的一道题除了要进行转换以外，还要十分注意每层循环的范围。   解释不了一点，直接挂一个我觉得写的比较好的博客吧。   (*´∇｀*) 欢迎回来！ (cnblogs.com)   //首先矩阵旋转90度，去除后效性。  //f[i][j][k]表示截止到第i行，总共已经选j个砖块，其中第i行已经选了前k个砖块的最大值。 //f[i][j][k]=max(f[i][j-k][p]+sum[i][k]){0<=k<=j,0<=p<k}  #include<cstdio> #include<cstring> #include&l...

//分组背包问题，首先考虑一个木板的情况： //对于一个木板而言：dp[i][j]，i表示当前是第i次粉刷，粉刷第j块格子的情况。 //那么得到状态转移方程为：dp[i][j] = max(dp[i-1][l]+num[l+1][j])。 //其中num[l+1][j]表示在l到j这个区间里面最大的有效格子是多少。 //然后将其扩展到多个木板即在一维加上木板。 //dp[k][i][j]。 //首选一次动态规划求出每一个木板涂i次的最好情况。 //dp[k][i][j] = max(dp[k][i-1][l]+num[l+1][j]); //然后用每个木...

本题如果想要直接去求的话需要对每一个物品去掉的情况进行一个01背包，这样的代价太大全部都会超时的。   那么我们将动态规划式子转换一下，某个物品去掉，背包容积在j下的种类数=背包容积在j下的种类数-某个物品一定要带，背包容积在j下的种类数。   那么某个物品一定要带的情况，其实相当于背包容积在j-a[i]情况下的种类数，然后将每个种类的背包装进a[i]容积的物品。   即可得到状态转移方程为：dp[j] = (f[j]%mod - dp[j-a[i]]%mod+10)%mod;   #include <bits/stdc++.h> using namespace...

双线动态规划问题，双线代表有两个状态在同时进行改变，并且互相会影响。   在本题中正反两个方向的传字条其实是一致的，也就是说从小轩到小渊的路径其实可以转化成从小渊到小轩的路径。这样可以将双线过程的起点保持一致。   然后我们设状态数组为：      其中i,j代表小渊纸条的坐标，k,l表示小轩纸条的坐标。那么他们的下一步过程有四种方式，要么都向下或都想右，又或者一下一右，一右一下。那么就可以得到状态转移方程为：     但在这时候还没有将这道题搞定，因为我们没有满足每个点只能被一个纸条走一次这个条件。对于这个条件我们首先观察在同一时刻也就是说走的步数一致的时候如果j和l相等的话一定意味着两个纸...

本题使用悬线法。   针对于每一点来说，他向上能到多长取决于上一个点的情况，如果上一个点与他相反那就h[i][j] = h[i-1][j]+1，否则的话就是 1。   那么对于每一个点左边最长是多少，右边最长是多少都能求出来。   然后我们可以看到在竖直方向会产生许多悬线，那么接下来去取这些悬线最大到左边和右边分别是多少。   最后的结果就是某个悬线可以形成的最大矩形，再根据面积公式计算即可。      #include <bits/stdc++.h> using namespace std; #define int long&nb...

本题讨论的是每一行的矩形的摆放，而一开始因为纠结于将一个矩形用一个二进制表示，但矩形摆放的方式不同每一行的数位也就不同所以思路就此卡住了。。。。。。   但我们从矩形的摆放方式将其定义成1和0，并且每一个边长为1的小格都有一个0或1，这样就保证了每一层二进制位数的相同，那么这样写的状态转移方程是什么样的呢？   我们从某一层来看，某一层可以如何摆放其实取决于上一层的摆放情况。   我们设、1：表示竖着摆放的积木   0：表示横着摆放的积木。   对于某一层来说如果上一层是1的话下一层一定是0，因为上一层是竖着放的那么下一层是不能放东西的，直接用0表示也可以，毕竟横着放本身对下一层也没有影响。 ...

本题算是状压dp的一个变形用法，在这里面将二进制位上的数从0变到1其实做得将牛放到末尾的操作，那么可以看到对于某一头牛他只关心前面一头牛是什么，前面牛到底有几种摆放方式和当前的牛无关。这符合动态规划的特性。   那么很容易得到状态转移方程为：dp[state|(1<<(i-1))][i] = dp[state|(1<<(i-1))][i]+dp[state][j]   值为方式数，放置的时候判断牛牛是否符合混乱即可。   //dp[state|(1<<(i-1))][i] = dp[state|(1<<(i-1))][i]+d...

本题状压dp的简单应用，用0表示还没有消失或没有被使用的气体，1表示已经使用的气体。   每次枚举寻找两个气体，饭后将其中一个变成1就行。   //在这里我们直接使用一维状态的转移，这样在转移的过程中去挑选值为0的两个节点 //那么这两个节点肯定有一个留下来，我们假设删除的节点为j，那么就有 //dp[state|(1<<(j-1))] = max(dp[state] + a[i][j]); #include <bits/stdc++.h> using namespace std; #define&n...

//动态规划数组依旧是：dp[state][j];i表示状态，j表示在当前状态下的结尾节点。 //但不同的在于这道题要找简单环，而对于找简单环来说定起点和终点是比较重要的。 //因为只有知道了起点和终点，然后又知道起点和终点是否有一条直接的线连接，就证明是不是环。 //如果我们单纯的去执行状态转移方程的话，将种类数设为值确实可以得到在某个状态i下，以j结尾的方式数。 //但我们不知道起点在哪里。 //但在这里，我们可以保证下一个点一定在最小的那个1，也就是以最小的1位为起点前面。 //这样只要某个状态下，某个点结尾成立，那么它的起点就一定是最小下标的那一1。 //而对于判断环路来说有一个起点和...

本题从众多郊区里面选取R个郊区，要求走过一遍之后的中距离最短，那么我们首先就是要得到R个郊区彼此之间的最短距离，然后根据这个最短距离再来安排怎么走合适。   那么要求彼此之间的最短距离问题就得用到数据结构里面学到的弗洛伊德算法了，根据弗洛伊德算法将所有的最短距离求出来。   那么问题就回归到了经典的TSP问题了，需要使用状压dp，建立一个状态转移数组：dp[i][j]，i是用二进制表示的状态，j是当前要最那一个郊区下手。   那么状态转移方法为：dp[state|st][k+1] = min(dp[state|st][k+1], dp[state][j+1] + a[play[j+1]][pl...

本题算是[SCOI2005]互不侵犯KING (nowcoder.com)这道题的升级版，在互不侵犯这道题里面除了同一行的限制，上下行的限制仅仅包含一行。而在这道题里面则是包含了两行。   那么我们可以像互不侵犯那样将状态转移数组设成dp[i][j]，i表示某一层，j表示当前层的二进制数吗？当然不行，因为就算在遍历的时候去判断当前和上一个以及上上个是否符合要求那他们的值也不具有相加性。   所以在这里我们将两层间的状态也一起维护了，状态转移数组设置成：dp[i][j][k]。i表示某一层，j表示当前层的二进制数，k表示上一层的二进制数。这样将两层间捆绑就可以将其值相加了。   还这题中除了简单...

本题需要在N*N个棋盘里面摆放上K个国王，国王需要互不侵犯。那么从这个矩阵的角度来看（果断dfs）（开玩笑的。   本题使用状压dp去求解，以每一层作为最外层遍历取走，对于每一层来说哪些格子上放的有国王就是1，没有放国王就是0，所以直接采用二进制去表示每一层的状态。   而到某一层为止到底能放多少国王取决于上一层的状态以及自身不能有侵犯发生。故采用二进制的位运算去判断。   最后状态转移方程为：dp[i][j][st[s].first] += dp[i-1][j-st[s].second][st[t].first];  #include <bits/stdc++.h> u...