Cod sursă (job #470970)

#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin("s2c.in");
ofstream fout("s2c.out");

const int VAL=2005;

int N, M, i, j, k;
int T, mx, v[VAL], last;
int dp[VAL][VAL], cnt;
int nr[2][VAL][VAL], ANS;
pair <int, int> P[VAL];

int main()
{
    fin >> T;
    while (T>0)
    {
        T--;
        fin >> N;
        for (i=1; i<=N; i++)
        {
            fin >> P[i].first;
            P[i].second=i;
        }
        if (N==1)
        {
            fout << 1 << '\n';
            continue;
        }
        sort(P+1, P+N+1);
        ANS=mx=0;
        for (i=1; i<=N; i++)
        {
            if (P[i].first!=P[i-1].first)
                mx++;
            v[P[i].second]=mx;
        }
        cnt=T % 2;
        for (j=1; j<=N; j++)
        {
            for (i=1; i<j; i++)
            {
                dp[i][j]=1+nr[cnt][v[j]-1][i];
                dp[i][j]=max(dp[i][j], 2);
                ANS=max(ANS, dp[i][j]);
                nr[cnt][v[i]][j]=max(nr[cnt][v[i]][j], dp[i][j]);
            }
            for (i=1; i<=max(mx, last); i++)
            {
                nr[cnt][i][j]=max(nr[cnt][i-1][j], nr[cnt][i][j]);
                nr[1-cnt][i][j]=0;
            }
        }
        last=mx;
        fout << ANS << '\n';
    }
    fin.close();
    fout.close();
    return 0;
}