8.23

· · 个人记录

T1

题目大意：

给定一个数，求1~n的每个数各位数字乘积最大值。

原思路:

数位dp，但是不知道哪错了。

正解:

贪心

如果要各位数字乘积最大，那肯定先考虑几个数+许多个9。
如果一个数是abcde。
那么最大的可能的值为：
1.(a-1)*9*9*9*9
2.a*(b-1)*9*9*9
3.a*b*(c-1)*9*9
4.a*b*c*(d-1)*9
5.a*b*c*d*(e-1)
但是10000就不适合用了，所以要判断现在是否为前导零，前导零就可以不算。

T2

题目大意：

给定一棵树，每个节点有一个点权，求这个点到根的路径的最大交错和，比如结点i的交错和为 a_i-a_{p_i}+a_{p_{p_i}}-\ldots，p_i表示i到根节点路径上的父节点。

原思路:

dfs每次算出i到根节点的路径，然后计算。

正解:

一个由上推到下的树形dp。
推一下式子，比如4~1的路径：
假设路径为4->3->2->1
a[4]-a[3]+a[2]-a[1]
=a[4]-(a[3]-a[2]+a[1])
那也就是a[4]-dp[3]; 因为需要最大，所以想到用这个点权-父节点的dp最小值。
所以要维护两个dp，一个最大交错和，一个最小交错和。 但是点权-父节点的dp最小值可能比点权还小，所以就找这两个最大的，最小值同理。

T3

题目大意：

给定一个无向图，保证无环，给定若干对点a,b，每次将a~b的路径经过次数加一，求所有边的经过次数。

原思路:

暴力dfs。

正解:

无向无环图，也就是树，所以考虑边差分，这个就不用多说，但是边差分是把边的值转移给点，每次都给两个点最深的那一个，所以将每个边的左右节点存下来，输出深度最大的那个节点。

T4

题目大意：

给定一个数组，每次执行操作：
选定一对相邻且相等的元素a_i和a_{i-1}，然后把他们改为a_i+1。
求数组能得到的最小可能长度。

原思路:

用链表暴力实现。

正解:

因为是区间选点，所以考虑区间dp，O(n^3)刚好能过。
dp[i][j]代表区间[i,j]能得到的最小可能长度。
判断能否合并就用一个数组代表区间操作后能变为一个数的那一个数，如果操作后不能变为一个数，那就为0。
区间dp需要遍历l,r和中间的一个断点mid，转移就看l\~mid操作后的那一个数是否与mid+1\~r操作后的那一个数，相同dp肯定就为1，不同就为l\~mid的dp值+mid+1\~r的dp值，改变的数就不用讲了。