566
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("%d\n",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("%d\n",ans);
}
}
最後更新：2017-04-04 07:03:15