cf 156.div2 C Almost Arithmetical Progression

     貌似是两周前的比赛，一直忙考试没写。

     C题就是找个最长的交替序列，直接模拟可以过，比赛的时候以为会超时就没写，刚写了下居然过了

     也可以用dp，dp[i][j]=dp[j][last]+1，last为最后一个和i相等的数下标，就是i和last是两个相同的数，中间加一个j为任意数

模拟代码：

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#define INF 1E9
using namespace std;
map<int,vector<int> > pos;
vector<int> all;
int main()
{
int n,i,j,t,ans;
while(~scanf("%d",&n))
{
ans=0;
pos.clear();all.clear();
for(i=0;i<n;i++)
{
scanf("%d",&t);
if(pos[t].size()==0)all.push_back(t);
pos[t].push_back(i);
}
int a,b,now,A,B,t;
bool flag=0;
sort(all.begin(),all.end());
for(i=0;i<all.size();i++)
{
A=all[i];
ans=max(ans,(int)pos[A].size());
for(j=i+1;j<all.size();j++)
{
B=all[j];
a=b=0;now=2;
while(a<pos[A].size()||b<pos[B].size())
{
t=pos[A][a]-pos[B][b];
flag=1;
while(t*(pos[A][a]-pos[B][b])>0)
{
if(t<0){a++;if(a==pos[A].size()){flag=0;break;}}
else {b++;if(b==pos[B].size()){flag=0;break;}}
}
if(flag)now++;
else break;
}
ans=max(now,ans);
}
}
printf("%dn",ans);
}
}

dp代码：

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#define INF 1E9
using namespace std;
int a[4001];
int dp[4001][4001];
int main()
{
int i,j,last,n,ans;
while(~scanf("%d",&n))
{
ans=0;
memset(dp,0,sizeof(dp));
for(i=1;i<=n;i++) scanf("%d",&a[i]);
for(i=1;i<=n;++i)
for(j=last=0;j<i;++j)
{
dp[i][j]=dp[j][last]+1;
if(a[i]==a[j])last=j;
ans=max(dp[i][j],ans);
}
printf("%dn",ans);
}
}

最后

以上就是炙热大船为你收集整理的cf 156.div2 C Almost Arithmetical Progression的全部内容，希望文章能够帮你解决cf 156.div2 C Almost Arithmetical Progression所遇到的程序开发问题。

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