Difficulty: 1800 ~ 2200
Tag : dp
1092F
题意
给一颗 $n$ 个节点的点权树，边权都为 $1$，问选择一个点 $v$，使得 $\sum_{i=1}^{n}(dis(i,v)·a_i)$ 最大( $a_i$ 为点权)
$(n \le 3·10^5)$
题解
考虑一棵树，其父节点转移到儿子节点，就是除了当前儿子节点的子树，到当前子树距离增加 $1$，当前子树的距离都减少 $1$，所以维护出每个节点所在子树的权值和及当前根的和后，再从上到下转移维护最大值即可。
1083A
题意
给一颗 $n$ 个节点的树，点和边都有权值，选择一条 链，使得 点权和-边权和 最大。
$(n \le 3·10^5)$
题解
所有题一定要注意 $n=1$ 的情况！
一条链的话，一个显然的dp就是，从儿子转移到儿子，但注意子树内部也可以成一条链。
若不要求一条 链 吧，则可以互相转移。
1067A
题意
给出 $n$ 个数的序列，其中一些数为-1(可以任意填充)，问使得
$a_1<=a_2$
$a_i<=max(a_{-1}, a_{i+1})(2<=i<=n-1)$
$a_{n-1}>=a_n$
$(n \le 10^5)$
满足的方案数。$(\rm mod$ $998244353)$
$(n \le 10^5,1\le a_i\le 200)$
题解
直接对每一位的情况进行 dp。
当前位置和前一位的关系有三种，分别讨论一下即可，注意要保证满足题目要求。
定义 $\rm dp[i][j][0/1/2]$:第 $i$ 个数为 $j$ ( $0$ :小于前面一个数， $1$ :等于前面一个数， $2$ : 大于前面一个数)。
remain code
1065D
题意
给出一个 $n · n$ 的矩阵，不重不漏地随机放着 $1$ 到 $n · n$ 的每个数。现在你站在数字 $1$ 的位置，每次可以有三种走法：
- 走直线，四个方向。一次可以走多个单位，不仅只能走到相邻的位置，就像中国象棋里的车。
- 走斜线，四个方向。一次可以走多个单位，像国际象棋里的象。
- 走日字，八个方向，一次只能走一个单位。就像中国象棋里的马。
每走一次，需要花费一个精力值。如果切换了一次走法，需要额外花费一个精力值。而且要求，必须先访问 $1$，再访问 $2$，然后是 $3$，以此类推，一直到 $n^2$，但是，在从 $i$ 走到 $i+1$ 的过程中，可以经过其它的点，比如在中途某个点停一下，换了走法，继续走。
问最少花费多少精力值可以走完 $n^2$ 个点。精力最小的时候要求切换走法次数也最少。
输出最小精力和最少切换走法次数。
$(n \le 10)$
题解
状压 $\rm dp$
- 定义: $dp[x][y][z][t][k]$ :表示在点 $(x,y)$ ，当前的走法为 $z$ ，已经换了 $t$ 中走法，已经到了 $k$ 个点的最小消耗。
- 转移：暴力 $bfs$ 转移即可。
1036C
题意
问区间 $\rm [l,r]$ 的数，满足非 $0$ 位数小于等于 $3$ 的数量。
$\rm (1\le l\le 10^{18})$
题解
经典的状压 dp
1025D
题意
给出 $n$ 个数的上升序列，若两个数的 $gcd>1$ 则可以连边，问这 $n$ 个数是否可以构成二叉搜索树。
二叉搜索树：左子树小于当前节点，右子树大于当前节点。
$(n \le 700，2 \le a_i \le 10^9)$