Also available: UVALive 6582, UVA 1642, Gym 100299C

题意

给定一个序列，定义一个连续子序列的 Magical GCD 为子序列内所有元素的 GCD 乘上区间长度，求最大的 Magical GCD。

比赛 ID: 2015

注：本题解参考代码均为 C++ 代码，如果你是 C 使用者，出现不认识的头文件时，若是 c 开头的，一般可以通过去掉开头的 c 然后在末尾添加 .h 来转换成 C 的头文件，如 cstdio 在 C 中为 stdio.h ，其他的请自行搜索。另外，如果出现不认识的写法，如 sort（排序） 、 stack（栈） 等，请自行实现。

比赛 ID: 2016

注：本题解参考代码均为 C++ 代码，如果你是 C 使用者，出现不认识的头文件时，若是 c 开头的，一般可以通过去掉开头的 c 然后在末尾添加 .h 来转换成 C 的头文件，如 cstdio 在 C 中为 stdio.h ，其他的请自行搜索。另外，如果出现不认识的写法，如 sort（排序） 、 stack（栈） 等，请自行实现。

解题思路

不难想到用 $dp[i][j]$ 表示放第 $i$ 个题时趣味值为 $j$ 的方案数，然而有一个问题是不好表示前面 $i-1$ 个都选了哪些。因此这里需要用状态压缩 DP（一看题目数量那么小就应该试图往状压那边想了），把我们的 dp 数组中的第一维表示为一种题目选择方案（按二进制压缩成一个数存储），然后就很容易写出转移方程（其中 $i$ 表示当前遍历到的状态，$j$ 和 $k$ 分别为 $[1, n]$ 及 $[0, m]$ 的循环，$cnt$ 为当前状态下的已选题目数量）：

$$dp[i+2^{j-1}][min(k+a[cnt+1][j], m)] += dp[i][k]$$

解题思路

使用费用流求解。首先把题中所有的边都按流量为 1，费用为路径长度加边，这样就保证了每条路只能走一次，且求出来的最小费用就是最短路径长度。之后再把源点到 1 以及 n 到汇点都加一条流量为 2，费用为 0 的边，这是为了支持题目中的往返操作。这样跑一边最小费用最大流即可求出答案。