题目：AT_abc274_d
题意
- 给定正整数数组 \(a\) 和整数 \(x,y\)，请判断是否有 \(n + 1\) 个点满足（一个坐标可以不止一个点）：
- \(p_1 = (0, 0), p_2 = (A_1, 0), p_{n + 1} = (x, y)\)。
- \(p_i\) 与 \(p_{i + 1}(2 \le i \le n)\) 的距离为 \(a_{i}\)
- 线段 \(p_ip_{i + 1}\) 与 \(p_{i + 1}p_{i + 2}(1 \le i < n)\)。
- 数据范围：\(1 \le n \le 10^3, 1 \le a_i \le 10, \mid x \mid, \mid y \mid \le 10^4\)。
思路
-
首先有一个暴力 \(DP\)，令 \(dp_{i, j, k}\) 表示第 \(i\) 个点能否在 \((j, k)\)，\(dp_{i, j, k}\) 转移到 \(dp_{i + 1, j', k'}，\)j', k'$ 满足题意要求，最后看 \(dp_{n + 1, x, y}\)，空间时间都爆了。
-
然后我们发现 \(j, k\) 是分开的，若 \(i\) 为偶数，\(x\) 变化，否则 \(y\) 变化，所以令 \(dp_{i, j}\) 表示第 \(i\) 个点变化坐标的那一维能否为 \(j\)，\(dp_{i,j}\) 转移到 \(dp_{i + 2, j'}, j' = j + a_{i - 1} 或 j - a_{i + 1}\)，若 \(n\) 为奇数，看 \(dp_{n + 1, x} \& dp_{n, y}\)，否则看 $dp_{n, x} & dp_{n + 1, y}，注意下标可能为负数，需要偏移。
时间复杂度
- 状态数：\(O(nx)\)。
- 转移数：\(O(nx)\)，一次转移 \(O(1)\)。
- 总时间复杂度：\(O(nx)\)。