https://codeforces.com/contest/1720/problem/D1
Problem - D1 - Codeforces
codeforces.com
a[i]가 200이하라길래 대충 2차원 dp거나 뭐 200개 관리하는 쪽으로만 생각하다가 못풀었다.
xor연산에 대한 관찰이 더 필요했다.
arr[i] xor j 는 j를 최대 200까지만 바꿀 수 있다. 반대로도 마찬가지.
따라서 dp[i] = max(dp[i - 400] ~ dp[i-1]) + 1 인데 사실 i - 255까지만 봐도 된다.
왜냐하면 i - 256 이하의 숫자들은 뒤에서 7번째 이상의 비트들만 놓고 봤을 때 이미 i보다 작다.
근데 200은 뒤에서부터 7개 비트만 건드리므로 뭘 해도 i보다 커질 수가 없기 때문이다.