题解 P2362 【围栏木桩】

苏黎世 · 2020-10-29 15:30:55 · 题解

这道题其实很简单，就是求一个最长上升子序列。

不同的是，还要求出最长的个数。

我们用一个s数组存个数，f数组存长度。

代码： 其实长整形不用开，只是我在调VSCode的时候用的

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
long long T, n, h[30], ans1, ans2, s[30], f[30];
int main()
{
    scanf("%lld", &T);
    while(T--)
    {
        scanf("%lld", &n);
        for(int i = 1;i <= n; ++i)
        {
            s[i] = 1;
            f[i] = 1;
        }
        ans1 = 0;
        for(int i = 1;i <= n; ++i)
        {
            scanf("%lld", &h[i]);

            for(int j = 1;j < i; ++j)
            {
                if(h[j] <= h[i])
                {
                    if(f[i] <= f[j])
                    {
                        f[i] = f[j] + 1;
                        s[i] = s[j];
                    }else
                    if(f[i] == f[j] + 1)
                        s[i] += s[j];

                }
            }
            if(f[i] >= ans1)
            {
                ans1 = f[i];
                ans2 = s[i];
            }
        }
        printf("%lld %lld\n", ans1, ans2);
    }
    return 0;
}