bfs + dp 好题。 真好，比赛的时候想不出来，看题解的时候感觉好复杂…… 看完写的时候感觉非常流畅！ 题意： 载人过岸，一艘船最大载重 k 已经给定。每个人的重量只会是50或者100。问最小的过岸次数与方案数。 思路： 老实说这个题目我可以看就知道是道搜索题，因为和那个什么东西(就是搜索入门的那个)来着非常像。 最重要的还是理清状态与思路。 以左岸50重人数，100重人数，船是否在左岸表示一个状态，对他进行 bfs ，只要满足船重量大于 0 并且小于等于最大 k，每次过岸花费 1 。第一个搜索到 最终状态的就是我们要求的结果。 而我们的方案数，只能通过dp来球，dp最讲求的就是状态， 转移方程如下： 如果是 左岸 — > 右岸 anum表示 50重总人数 ， bnum 表示 100重 总人数 ( dp[x][y][0]…
真是天真了，在计算器上计算复杂度在 1e8 ,给了 3s 时间以为侥幸能过，就用暴力写了……
结果拖到最后也没有写出来……
传送门
题意：
计算最大的有空行的弓形矩阵值。
思路：
如果说你观察仔细的话，你会发现 5×5 方阵 与 3×3 的方阵 差一个格子互补， 7×7 的 方阵 与 5×5 的方阵 差一个格子互补， 9×9 的 方阵 与7× 7 的方阵 差一个格子互补……
那么我们先预处理好每一个 3×3 方阵的值，再通过递推就能知道每一个方阵的值了
AC Code
#include
传送门
题意：
给你一个无向图，保证联通并且没有环（实质上就是一棵树……），要求：
每个点移动到另一个点去，并且不可能会有两个点移动到同一个点去，求最大移动距离和。
思路：
队友告诉我是图论……
…………
然后我特么还信了……
……………………
在看到结点个数达到 1e5 的时候我就应该意识到，基本不会是什么图论算法了。
我们可以这么想，先只考虑一半的节点移动到另一半的节点。
再是我们得确认一点，假如我可以得到这棵树的重心，那么重心一边的节点必然得移动到重心另一边的节点去才能使得移动距离和最大。（这个是显然的吧……举个例子 a-b-c-d a->c 必然会比 a->b 距离和大，而且，a->b影响的是 a,b 两个节点。）
然而我们无法轻松找到一棵树的重心，但是，我们从每一条边进行考虑，要使移动距离和最大，由该边断开形成的两棵子树，节点数目小的那一棵必然会全部移动到结点数目更多的那一棵，因为树的重心必然在节点数目更多的那一棵子树上，而且反过来移动也是不可能的吧…………
于是我们只要一次dfs就好了……
#include
以前在暑假集训的时候搞得最多的还是图论相关，如果碰到树形结果很多时候就直接用搜……当然绝大多数时候也都T了……（当时也不喜欢分析复杂度，真是个坏习惯……
树形DP，简单说还是在树上做决策，只要把基础DP掌握好了我想应该不会是什么难事，只是换个场地罢了……
0. 入门题 POJ 2342
题意：
某公司要举办一次晚会，但是为了使得晚会的气氛更加活跃，每个参加晚会的人都不希望在晚会中见到他的直接上司，现在已知每个人的活跃指数和上司关系（当然不可能存在环），求邀请哪些人（多少人）来能使得晚会的总活跃指数最大。
思路：
定义数组dp[maxn][2],dp[k][0]表示第 k 人不去，dp[k][1] 表示第 k 人去。定义 son 为第 K 人的某个下属
我们从下往上分析，对于第 K 个人有以下去与不去两种情况
* 假如 K 参加，…