#include <stdio.h>
#define N 5010
int n;
int a[N];
int len[N];
int num[N];

int main()
{
        int i;
        int j;
        int maxlen;
        int ans;
        while(scanf("%d", &n) != EOF) {
                for(i = 1; i <= n; i++)scanf("%d", &a[i]);
                len[1] = 1;
                num[1] = 1;
                for(i = 2; i <= n; i++) {
                        len[i] = 1;
                        num[i] = 1;
                        for(j = 1; j < i; j++) {
                                if(a[j] > a[i] && len[j] + 1 > len[i]) {
                                        len[i] = len[j] + 1;
                                        num[i] = num[j];
                                } else if(a[j] > a[i] && len[j] +1 == len[i]) {
                                        num[i] += num[j];
                                } 
                        }
                        for(j = i - 1; j >= 1; j--) {
                        //此处，如果发现前边与自己相同的而且最大长度也相同，则把前边那个的最大长度的数目置为0，因为后边的那个一定能覆盖前边那个的所有情况的
                                if(a[j] == a[i] && len[j] == len[i]) {
                                        num[j] = 0;
                                        break;
                                }
                        }
                }
                maxlen = len[n];ans = num[n];
                for(i = n - 1; i >= 1; i--) {
                        if(len[i] > maxlen) {
                                maxlen = len[i];ans = num[i];
                        } else if(len[i] == maxlen) ans += num[i];
                }
                printf("%d %d\n", maxlen, ans);
        }
        return 0;
}

• Beautiful！~ (28) Findxiaoxun 2013-09-12 09:36:38