Cod sursă (job #333613)

#include <fstream>
using namespace std;
ifstream f("s2c.in");
ofstream g("s2c.out");
int t,n,i,j,a[1<<11],fr[1<<15];
short dp[1<<11][1<<11];
int main()
{
    f>>t;
    while(t--)
    {
        f>>n;
        for(i=1;i<=n;++i) f>>a[i],fr[a[i]]=1;
        for(i=1;i<=30000;++i) fr[i]+=fr[i-1];
        for(i=1;i<=n;++i) a[i]=fr[a[i]];
        for(i=1;i<=30000;++i) fr[i]=0;
        for(i=1;i<=n;++i)
            for(j=1;j<=n;++j) dp[i][j]=0;
        int ans=1;
        for(i=1;i<=n;++i)
        {
            dp[i][0]=1;
            for(j=1;j<=n;++j)
                dp[i][j]=max(dp[i][j],dp[i][j-1]);
            for(j=i+1;j<=n;++j)
            {
                int nr=dp[i][a[j]-1]+1;
                ans=max(ans,nr);
                dp[j][a[i]]=nr;
            }
        }
        g<<ans<<'\n';
    }
    return 0;
}