BZOJ3357:[Usaco2004]等差数列 dp

思路:

我们令\(f[i][j]\)表示等差数列最后两项的下标分别为\(i,j\)时的最长长度.

显然我们有:

\[f[i][j]=max_{k=1}^{i-1}\{f[k][i]+1\}(2a[i]=a[j]+a[k])\]

重要的就是如何快速找出\(k\)的位置.

我们呢就可以将权值离散化,记录一下每个权值在序列中出现的位置.

于是我们要找的\(k\),显然就是权值相同时标号小于\(i\)且最大的一个.

因此我们维护一个vector然后二分就好了.

(注意\(n=1\)233)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
using namespace std;
 
#define N 2010
vector<int>v[N];
 
int a[N],b[N],id;
map<int,int>M;
 
int f[N][N];
 
int main(){
    int n;scanf("%d",&n);if(n==1){puts("1");return 0;}register int i,j;for(i=1;i<=n;++i)scanf("%d",&a[i]),b[i]=a[i];
    sort(b+1,b+n+1);for(b[0]=-1<<30,i=1;i<=n;++i)if(b[i]!=b[i-1])M[b[i]]=++id;
    for(i=1;i<=n;++i)v[M[a[i]]].push_back(i);
    int nowv,ins,siz;
    for(j=2;j<=n;++j){
        for(i=1;i<j;++i){
            f[i][j]=2;
            nowv=M[2*a[i]-a[j]];
            if(nowv){
                siz=v[nowv].size();
                if(v[nowv][0]<i){
                    int L=0,R=siz-1,mid;
                    while(L<R){
                        mid=(L+R+1)>>1;
                        if(v[nowv][mid]<i)L=mid;else R=mid-1;
                    }f[i][j]=max(f[i][j],f[v[nowv][L]][i]+1);
                }
            }
        }
    }
    int res=0;for(i=1;i<=n;++i)for(j=i+1;j<=n;++j)res=max(res,f[i][j]);
    printf("%d",res);
    return 0;
}