传送门 马走日， 象走田，车走直路炮翻山，小艾同学发明了新玩法，只用炮来布阵棋盘，在一个N*M 的棋盘上，你要放置若干个炮兵，可以是0个，但是不能让炮打到彼此，有多少种方案？ 思路：按行dp，思考一下可以发现只需要知道有几列是已经有1个炮，有几列已经有两...

传送门 题目大意：给定n个点m条边的无向图，每个点作为初始位置的概率相同，在每个点时走向相连每个点的概率相同。一共走d步，问从不经过每个点的概率。 思路：概率dp，定义dp[u][i][j]：经过了j步之后落在i点且从来不经过u点的概率。最后对于各个点，从不经过它...

传送门 这是找树的重心的经典题目。 题目大意：在一棵树中找一个点，删掉以后使所有子树中最大的节点数最少，问应该删哪个点以及最大子树的节点数。 思路：树形dp，f[u]保存以u为根节点的子树的节点数，那么只要比较答案和f[v]+1和n-f[u]-1的关系就可以了。 dfs一...