Codeforces 255C

题意略。

本题考查动态规划，顺便考查一下优化。

这个题目可以归约到最长递增子序列那一类，定义状态：dp[i][j] --- 当前以第i个数结尾，前一个数是第j个数的最长序列。

if(a[i] == a[k]) dp[i][j] = dp[j][k] + 1;

这里不用再去枚举k了，因为从小到大枚举j时可以顺便寻找k。

#include<bits/stdc++.h>
#define maxn 4050
#define maxn2 1000005
using namespace std;
int dp[maxn][maxn],store[maxn];
int maxx[maxn2];
int main(){
int n,ans = 0;
scanf("%d",&n);
for(int i = 1;i <= n;++i){
scanf("%d",&store[i]);
}
dp[0][0] = 1;
for(int i = 1;i <= n;++i){
int k = -1;
for(int j = 0;j < i;++j){
if(k == -1){
if(j > 0) dp[i][j] = 2;
else dp[i][j] = 1;
}
else{
dp[i][j] = max(dp[i][j],dp[j][k] + 1);
}
if(j > 0 && store[i] == store[j]) k = j;
ans = max(ans,dp[i][j]);
}
}
printf("%dn",ans);
return 0;
}
/*
10
1 3 2 4 5 2 6 2 5 6
*/