CF1720D1 题解

## 前言 [题目传送门！](https://www.luogu.com.cn/problem/CF1720D1) [更好的阅读体验？](https://liangbowen.blog.luogu.org/solution-cf1720d1) 有点思维难度的 DP 优化题。 ## 小知识 在做这道题之前，你需要知道：$x - y, y - x \le x \oplus y \le x + y$。 证明非常简单，利用异或的性质即可。 ## 思路 容易想到类似 LIS 的东西。设 $dp_i$ 表示以 $i$ 下标元素结尾，最长子序列长度，有： $$dp_i = \max\limits_{j=1}^{i-1}\left[a_j \oplus i < a_i \oplus j\right] \{dp_j + 1\}$$ 注意下标，如题从 $0$ 开始。 然后我们得到一个 $O(n^2)$ 的 DP。题目告诉我们 $a_i$ 较小，必定有端倪。于是尝试对 $a_j \oplus i < a_i \oplus j$ 化简。 根据上面的引理，可得：$i - a_j < a_i + j$。进而得 $i - j < a_i + a_j \le 200 + 200 = 400$。 进一步地，$i- j \le 400$ 可以得出 $j \ge i - 400$。 故，枚举 $i$ 后，$j$ 只需枚举 $\max\{0, i - 400\}$ 到 $(i - 1)$ 就够了。 时间复杂度 $O(k n)$，其中 $k$ 为 $400$。$(3 \times 10^5) \times 400 = 12 \times 10^7 = 1.2 \times 10^8$。 有点大，但其余常数极小，并且没有极限数据，因此能过。 ## 完整代码 ```cpp #include <iostream> #include <cstdio> #define endl putchar('\n') using namespace std; int read() { char op = getchar(); int x = 0, f = 1; while (op < 48 || op > 57) {if (op == '-') f = -1; op = getchar();} while (48 <= op && op <= 57) x = (x << 1) + (x << 3) + (op ^ 48), op = getchar(); return x * f; } void write(int x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + 48); } const int N = 3e5 + 5; int a[N], dp[N]; void solve() { int n = read(), maxn = 0; for (int i = 0; i < n; i++) a[i] = read(), dp[i] = 1; //注意要按题目的下标来 for (int i = 0; i < n; maxn = max(maxn, dp[i]), i++) //稍微严重的压行，意思是 maxn = max{ dp[i] } for (int j = max(i - 400, 0); j < i; j++) if ( (a[j] ^ i) < (a[i] ^ j) ) //需要注意，小于号两边的异或运算都要加括号，避免优先级错误 dp[i] = max(dp[i], dp[j] + 1); write(maxn), endl; } int main() { int T = read(); while (T--) solve(); return 0; } ``` 希望能帮助到大家！