codeforces255C.Almost Arithmetical Progression

题意：求出最长的i j i j i…j(i) 序列的长度
思路：先把各个数字离散化成1-n的形式，可以减少内存的使用，方便动态规划处理，然后用 dp[i][j] 表示最后两位为i j 的最大长度

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
int dp[4005][4005];
const int sz=1e6+5;
int order[sz];
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int ans=0;
int n;
cin>>n;
vector<int> b(n+1);
set<int> st;
for(int i=1;i<=n;i++){
cin>>b[i];
st.insert(b[i]);}
if(n<=2)cout<<n<<endl;
else{
int k=1;
for(auto it:st){
order[it]=k;
k++;
}
for(int i=1;i<=n;i++){
b[i]=order[b[i]];
}
for(int i=1;i<=n;i++){
bool flag=0;
for(int j=i-1;j>=0;j--){
if(b[i]==b[j]){
if(flag)continue;
flag=1;
dp[b[i]][b[j]]++;
ans=max(ans,dp[b[i]][b[j]]);
}
else{
dp[b[i]][b[j]]=max(dp[b[i]][b[j]],dp[b[j]][b[i]]+1);
ans=max(ans,dp[b[i]][b[j]]);
}
}
}
cout<<ans+1<<endl;
}
}

最后

以上就是腼腆芝麻为你收集整理的codeforces255C.Almost Arithmetical Progression的全部内容，希望文章能够帮你解决codeforces255C.Almost Arithmetical Progression所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。