Codeforces 255C Almost Arithmetical Progression DP

点击打开链接

题意:n个数b[i],定义序列a[i]=a[i-1]+(-1)^(i+1) *q (i>2,q为常量)
n<=4e3,b[i]<=1e6,问b中,子序列满足定义的最长长度?

合法的序列形式为 x,x+q,x,x+q,x.. .
x,x+q 下一个出现的x 一定为第一次出现在x+q之后的x(显然更优)
//怎么快速找到下一个x? b[i]<=1e6,用vector保存每个b[i]的位置,则对v[x] 二分找到第一个下标>j的x

不用二分...从后往前推时,用pos记录J之后第一个和b[i]相等的位置 
则设状态dp[i][j] 以i,j开头的最长子序列 dp[i][j]=dp[j][pos]+1
复杂度O(N^2)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
const int inf=1e9;
const int N=2e6+20;
const int M=4e3+20;
int b[N],n;
vector<int> v[N];
int dp[M][M];
int main()
{
while(cin>>n)
{
for(int i=0;i<=1e6;i++)
v[i].clear();
for(int i=1;i<=n;i++)
scanf("%d",&b[i]),v[b[i]].push_back(i);
int ans=0;
if(n==1)
{
cout<<n<<endl;
continue;
}
memset(dp,0,sizeof(dp));
for(int i=n;i>=1;i--)
{
int pos=-1;
for(int j=n;j>=i+1;j--)
{
if(pos==-1)
dp[i][j]=2;
else
dp[i][j]=dp[j][pos]+1;//posΪjÖ®ºóµÚÒ»¸ö³öÏÖµÄb[i]
if(b[j]==b[i])
pos=j;
ans=max(ans,dp[i][j]);
}
}
cout<<ans<<endl;
}
return 0;
}

最后

以上就是要减肥雪碧为你收集整理的Codeforces 255C Almost Arithmetical Progression DP的全部内容，希望文章能够帮你解决Codeforces 255C Almost Arithmetical Progression DP所遇到的程序开发问题。

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