Hasan and his lazy students最长子序列codeforce102163

题目连接

Hasan is teaching Dynamic Programming to his students at NCD. However, he feels they aren't studying what he is giving them, so he decided to test them on the NCDPC. He will give them an array of length NN, and they must tell him how many Longest Increasing Subsequences are in the array.

For example, if the array is (11 22 11 44 33). The LIS's length is 33, and it could be (11 22 44) or (11 22 33), so the answer is 22. Note that you can't choose (11 11 33) because it must be a strictly increasing subsequence, and you can't choose (11 22 33 44) because you can't change the order of a subsequence.

Input

First line of the input will be TT, number of test cases.

Each test case starts with NN, the size of the array, next line contain NN space separated integers, the array.

1≤N≤1000,1≤Ai≤1061≤N≤1000,1≤Ai≤106

Output

For each test case print one line, the length of the LIS and the number of LISes. As this number may be very large, print it module 109+7109+7

Example

input

Copy

3
5
1 3 2 3 1
3
1 2 3
7
1 5 6 2 1 4 1

output

Copy

3 1
3 1
3 2

这题一看就知道需要用最长上升子序列，但是有一个问题，需要记录所有的长度的个数，

这里就需要对最长上升子序列有非常深入的理解

Hasan and his lazy students最长子序列codeforce102163

最长上升子序列的时间复杂的为n^2，他会把0到i的每一个数j都与i比较，如果就a[j]a<a[i] dp[i]=dp[j]+1;

当处理到i时前面的总是最优的，这时我可以在比较的同时用一个sum[][]数组记录i个数的不同深度的所有个数,

比如 1 2 2 3

当处理2的时候sum[i][dp[j]+1]=所有的第j个数dp[j]长度的个数sum[j][dp[j]]+i个元素dp[i]+1长度的个数

这样从头到尾处理一次，就能的到结果

观学长代码后对最长子串有了更多的了解

//插入学长的代码
#include <iostream>
#include <cstring>
using namespace std;
int sum[1005][1005];
int mod = 1000000007;
int dp[1005];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        memset(sum,0,sizeof(sum));
        memset(dp,0,sizeof(dp));
        cin>>n;
        int res=0;
        int a[1005];
        for(int i=1; i<=n; i++)
        {
            cin>>a[i];
            dp[i]=sum[i][1]=1;
            for(int j=1; j<i; j++)
            {
                if(a[j]<a[i])
                {
                    if(dp[j]+1>=dp[i])
                    {
                        dp[i]=dp[j]+1;
                    }
                    sum[i][dp[j]+1]=(sum[i][dp[j]+1]+sum[j][dp[j]])%mod;
                }
            }
            res=res>dp[i]?res:dp[i];
        }
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            ans=(ans+sum[i][res])%mod;
        }
        cout<<res<<" "<<ans<<endl;
    }
    return 0;
}

坚持努力不放弃

Hasan and his lazy students最长子序列codeforce102163

相关推荐