D1. Xor-Subsequence (easy version)

D1. Xor-Subsequence (easy version)

https://codeforces.ml/problemset/problem/1720/D1

题意

给你长度为n的数组a 让你找出a最长的子序列满足 \(a_b_p * b_p+1 < a_b_p+1 * b_p\)
即这个子串相邻的两个数 \(ai aj\)满足\(i < j\) 且 \(a_i * j < a_j * i\)
这是简单版本 \(a_i<=200\)

思路

因为给定了\(a_i\)的大小最大不超过200 200的二进制位最高位为第8位 即亦或上一个\(a_i\)只会最多影响最右边的八位
而这八位最大的数就是 11111111 即255 对于第\(a_i\) 他不可能由他以前>255的数转移过来 所以很多都是不必要的

dp方程：
dp[i] : 前i个第i个取最多有几个
if \(a_i * j < a_j * i\) \(dp[i] = dp[i - j] + 1\)
最后取最大的dp[i]为答案

#include<bits/stdc++.h>
#define ll long long
#define all(a) a.begin(),a.end()
using namespace std;

const int N = 3e5 + 5;
const int M = 1e6 + 1;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;

int n;
ll a[N], dp[N];

void solve() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i <= n; i++) dp[i] = 1;
    for (int i = 1; i < n; i++) {
        for (int j = i - 1; j >= max(i - 255, 0); j--) {
            if ((a[j] ^ i) < (a[i] ^ j)) dp[i] = max(dp[i], dp[j] + 1);
        }
    }
    
    ll ans = 0;
    for (int i = 0; i < n; i++) ans = max(ans, dp[i]);
    cout << ans << "\n";
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int _t = 1;
    cin >> _t;
    while (_t--)
        solve();
    return 0;
}