计蒜客 单调减子序列

从一个由 NN 个整数排列组成的整数序列中，自左向右不连续的选出一组整数，可以组成一个单调减小的子序列（如从 [68, 69, 54, 64, 68, 64, 70, 67, 78, 62, 98, 87][68,69,54,64,68,64,70,67,78,62,98,87] 中我们可以选取出 [69, 68, 64, 62][69,68,64,62] 这个子序列；当然，这里还有很多其他符合条件的子序列）。给定整数序列的长度和整数序列中依次的值，请你求出这个整数序列中“最长的单调减小的子序列的长度”以及“值不同但长度都是最长得单调减小的子序列的数量”。

输入格式

输入第 11 行为一个整数 NN，表示输入的整数序列的长度（1 leq N leq 50001≤N≤5000）。接下来会输入 NN 个整数（可能为一行或多行），每个整数都在 3232 位带符 长整型范围内。

输出格式

输出包括一行，为两个数字，分别为针对给定的整数序列求出的“最长的单调减小的子序列的长度”以及“值不同但长度都是最长得单调减小的子序列的数量”。

样例输入

样例输出

代码：

#include

#include

long long a[5004],dp[5004];

int main()
{
    for(int i = 0 ; i         dp[i] = 1;
    int n,max = 1;
    scanf(“%d”,&n);
    for(int i = 0; i         scanf(“%d”,&a[i]);

    for(int i = n – 2; i >= 0; i–)
    {
        for(int j = n-1; j > i; j–)
        {
            if(a[i] >= a[j] && dp[i]             {
                dp[i] = dp[j] + 1;
                if(dp[i] > max)
                    max = dp[i];
                //printf(“%d %dn”,i ,dp[i]);
            }
        }
    }
    //for(int i = 0; i         //printf(“%d “,dp[i]);
    int sum = 0;
    for(int i = 0; i         if(max == dp[i])
            sum++;
    printf(“%d %d”,max,sum);
}