程序员人生 网站导航

BZOJ 3357 Usaco2004 等差数列 动态规划

栏目:php教程时间:2015-03-18 10:22:03

题目大意:给定1个长度为n的序列,求最大等差子序列

令f[i][j]表示当前等差数列最后1个数为a[i],倒数第2个数为j的最长长度

则有f[i][a[j]]=max{2,f[j][a[j]*2-a[i]]+1}

注意n=1时输出1

时间复杂度O(n^2logn)

#include <map> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 2020 using namespace std; int n,ans,a[M]; map<int,int> f[M]; //f[i][j]表示当前等差数列最后1个数为a[i],倒数第2个数为j的最长长度 int main() { int i,j; cin>>n; if(n==1) return cout<<1<<endl,0; for(i=1;i<=n;i++) scanf("%d",&a[i]); for(i=1;i<=n;i++) for(j=1;j<i;j++) { f[i][a[j]]=max(f[i][a[j]],2); f[i][a[j]]=max(f[i][a[j]],f[j][a[j]*2-a[i]]+1); ans=max(ans,f[i][a[j]]); } cout<<ans<<endl; return 0; }


------分隔线----------------------------
------分隔线----------------------------

最新技术推荐