洛谷 P2362 围栏木桩

题目描述

某农场有一个由按编号排列的n根木桩构成的首尾不相连的围栏。现要在这个围栏中选取一些木桩，按照原有的编号次序排列之后，这些木桩高度成一个升序序列。所谓的升序序列就是序列中的任何一个数都不小于它之前的任何一个数。试编写程序从这个围栏中选取合适的木桩使得选出的木桩个数t最大，并求出选取出t根木桩的方案总数c。

输入输出格式

输入格式：

文件中的第一行只有一个数m，表明随后有m个问题的描述信息。每个问题的描述信息格式为n h1,h2,h3,…,hn（其中hi（i=1,2,3,…,n）表示第i根木桩的高度。）

输出格式：

依次输出每个问题中t和c的解。每行输出一个问题的解。

输入输出样例

输入样例#1：

3

9 10 1 9 8 7 6 3 4 6

3 100 70 102

6 40 37 23 89 91 12

输出样例#1：

4 1

2 2

3 3

说明

m\le 5,n\le 20,h_i\le 150m≤5,n≤20,h​i​​≤150

序列dp

dp入门中。。

屠龙宝刀点击就送

#include <cstring>

#include <cstdio>

int max(int a,int b) {return a>b?a:b;}

int Max,m,f[],h[],ans[];

int main()

{

    scanf("%d",&m);

    for(int n;m--;)

    {

        scanf("%d",&n);

        int Max=;

        memset(f,,sizeof(f));

        memset(ans,,sizeof(ans));

        for(int i=;i<=n;i++)

            scanf("%d",&h[i]),f[i]=,ans[i]=;

        for(int i=;i<=n;i++)

        {

            for(int j=i-;j>=;j--)

            {

                if(h[i]>=h[j])

                {

                    if(f[i]<f[j]+)

                    {

                        f[i]=f[j]+;

                        ans[i]=ans[j];

                    }

                    else if(f[i]==f[j]+)

                        ans[i]++;

                }

            }

        }

        int Ans=;

        for(int i=;i<=n;i++)

        {

            if(f[i]==Max) Ans+=ans[i];

            else if(f[i]>Max)

            {

                Max=f[i];

                Ans=ans[i];

            }

        }

        printf("%d %d\n",Max,Ans);

    }

    return ;

}