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;
}
标签:const,int,ll,Subsequence,version,easy,Xor,dp,D1
From: https://www.cnblogs.com/yaqu-qxyq/p/16759539.html