D2.md

D2.T1 AtCoder - agc010_d

题意：

一个 $gcd$ 为 $1$ 的正整数序列。两人轮流操作，每次选择一个 $>1$ 的数 $-1$；然后序列中的所有元素除以它们的 $gcd$。 不能操作者输。

D2.T2 AtCoder - agc035_d

题意：

给定一个长度为 $N$ 的数列 $A$ ，每次操作可以选择其中连续的三项，权值依次为 $a,b,c$，将其替换为 $a+b,c+b$ 这两项。 求经过操作最后剩下的两个数的和的最小值。

题解：

极其巧妙的区间 DP。

考虑我们最后一次删除结点 i 的情况，那么 $i$ 号点的贡献系数是 $2$。

再递归考虑左区间的贡献，那么一个点向左合并出去一次将获得系数 $1$ ,向右出去一次将获得系数 $2$。设左区间最后删的结点是 $j$，那么 $j$ 号点的贡献系数一定是 $3$（左贡献系数加右贡献系数），再往下递归的时候，$[1,j-1]$ 的左系数是 $1$，右系数是 $3$；$[j+1, i-1]$ 的左系数是 $3$，右系数是 $2$.....递归下去。

设 $f[i][j][cl][cr]$ 表示，区间 $[i,j]$ 消掉，合并到区间左边那个点的系数是 $cl$,右边那个是 $cr$的最小开销。状态转移方程： $$ f[i][j][cl][cr] = min{f[i][p-1][cl][cl+cr] + f[p+1][j][cl+cr][cr] + a[p]*(cl+cr)} $$ 时间复杂度：$T(n)=\sum T(i)[i\le n] = O(3^n)$，评测链接：AC Submission。

D2.T3 AtCoder - agc027_f

题意：

给定两棵 $N$ 个节点的树 $A,B$，你需要执行若干次操作，每次操作选择 $1$ 个 $A$ 的叶子 $v$，删掉与其相邻的边，并加 $1$ 条边连接 $v$ 和另 $1$ 个点，每个点只能被选择 $1$ 次。请操作最少的步数使 $A,B$ 相同。

考虑枚举第一个移动的点和它移动到了哪个点 ($O(n^2)$)，然后贪心地把 $n-$整个连通块 作为答案（显然这样可以），然后要 $O(n^2)$ 判断合法性。

复杂度：$Tn^4$，评测链接：AC Submission。