题解 P2362 【围栏木桩】

江屿 · 2017-06-27 07:45:16 · 题解

这道题真心水，但就是输出卡死一堆人（原来），然后题目输出改了，于是就有人举报我的这篇题解了（生气）。

我不管我就是要再发一遍。

我是用三个数组来实现这道题的。

第一个数组a[i]表示数列的第i个数。

第二个数组b[i]表示第i个数的最长不下降子序列的长度。

第三个数组c[i]表示在这个数i之前都满足长度为b[i]的不同的子序列的个数。

统计完之后累加就好了。

//不过输出坑人。

//不是空格，而是五个单位长度的格子，所以用printf输出，是%5d，但这样是把格子空在左边，还是不行，所以就空去右边，成了%-5d，

//就ac了。

现在是直接输出%d %d\n就好了。

举报我的回来再看看，气死你气死你气死你。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 420000
using namespace std;
int n,m,a[N],b[N],c[N],ans;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&m);
        memset(a,0,sizeof(a));
        memset(c,0,sizeof(c));
        scanf("%d",&a[1]);
        for(int i=1;i<=m;++i){
            b[i]=1;
            c[i]=1;
        }
        for(int j=2;j<=m;++j){
            scanf("%d",&a[j]);
            for(int k=j-1;k>=1;k--)
                if(a[j]>=a[k]){
                    if(b[j]<b[k]+1){
                        b[j]=b[k]+1;
                        c[j]=c[k];
                    }
                    else
                        if(b[j]==b[k]+1)
                            c[j]++;
                }
        }
        int mmax=-1;
        for(int j=1;j<=m;++j){
            if(b[j]==mmax)
                ans+=c[j];
            else{
                if(b[j]>mmax){
                    ans=c[j];
                    mmax=b[j];
                }
            }
        }
        printf("%d %d\n",mmax,ans);
    }
    return 0;
}