路徑記錄的DP，地址：http://acm.pku.edu.cn/JudgeOnline/problem?id=1952
#include <stdio.h>

const int LEN = 5005;

int hash[40000];//HASH函數

void init ()
{

    for ( int i=0; i<40000; i++ )
    {
        hash[i] = 0;
    }
}

int num[LEN];

int dp[LEN][2];

int count = 1;

void cup ( int n, int *length, int * number )
{

    dp[n-1][0] = 1;//記錄最長的序列
    dp[n-1][1] = 1;//記錄方案數目
    *length = 1;
    for ( int i=n-2; i>=0; i-- )
    {
        int max = 0;
        for ( int j=i+1; j<n; j++ )
        {
            if ( num[i] > num[j] && dp[j][0] > max )
            {
                max = dp[j][0];
            }
        }
        dp[i][0] = max + 1;
        if ( dp[i][0] == 1 )
        {
            dp[i][1] = 1;
        }
        else
        {
            dp[i][1] = 0;
            for ( j = i+1; j<n; j++ )
            {
                if ( num[i] > num[j] && dp[j][0] == max && hash[ num[j] ] != count )
                {
                    dp[i][1] += dp[j][1];
                    hash[ num[j] ] = count;
                }
            }
            count ++;
        }
        if ( dp[i][0] > *length )
        {
            *length = dp[i][0];
        }
    }

    *number = 0;
    for ( i=0; i<n; i++ )
    {
        if ( dp[i][0] == *length && hash[ num[i] ] != count )
        {
            *number += dp[i][1];
            hash[ num[i] ] = count;
        }
    }
    count ++;
}

int main ()
{

    int n;

    init ();
    while ( scanf ( "%d", &n ) != EOF )
    {
        for ( int i=0; i<n; i++ )
        {
            scanf ( "%d", &num[i] );
        }

        int length, number;
        cup ( n, &length, &number );

        printf ( "%d %d\n", length, number );
    }
    return 0;
}