1. 题目

传送门= ̄ω ̄=

2. 题解

一开始看错题以为是统计条数不用判重。。。
统计最长下降子序列条数且不能有重复序列。。。
最先想到hash一下。。。
可是显然,$2^{31}$次方连int都存不下。。。你一个个数出来还不gg。。。

设$f(i)$为以第$i$个数字结尾的最长下降子序列长度,$cnt(i)$为以第$i$个数字结尾的最长下降子序列的条数(不重复),$arr[i]$为第$i$个位置上的数字。

不难发现对于第$i$个数字,状态从第$j$个数字转移过来,如果能让$f(i)$更新那么就直接让$cnt(i)=cnt(j)$。否则:如果$f(i)==f(j)+1$则判断是否已经用数字$arr[j]$更新过$f(i)$了,如果没有则让$cnt(i)+=cnt(j)$。

这样搞个set哈希一下就可以了。
但是会TLE啊!因为要不停地更新$f(i)$,不停地清空set。

仔细想想,可以看出如果有两个相同的数字,一个在位置$x$,一个在位置$y$,且$x<y<i$,那么如果能用$f(x)$更新$f(i)$,就一定能用$f(y)$更新$f(i)$。换而言之,如果不能用$f(y)$更新$f(i)$,就一定不能用$f(x)$更新$f(i)$。

所以找最长下降子序列时枚举$j$时从大到小枚举就行了,就不用更新$f(i)$时清空set了。

于是就AC了= ̄ω ̄=

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n,arr[5005],f[5005],cnt[5005],ans1,ans2;
set<int> book;
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&arr[i]);
    for(int i=1;i<=n;i++)
    {
        f[i]=cnt[i]=1,book.clear();
        for(int j=i-1;j>0;j--)
            if(arr[i]<arr[j])
            {
                if(f[i]<f[j]+1)f[i]=f[j]+1,book.insert(arr[j]),cnt[i]=cnt[j];
                else if(f[i]==f[j]+1&&!book.count(arr[j]))
                    cnt[i]+=cnt[j],book.insert(arr[j]);
            }
    }
    book.clear();
    for(int i=n;i>=1;i--)
        if(f[i]>ans1)book.insert(arr[i]),ans1=f[i],ans2=cnt[i];
        else if(f[i]==ans1&&!book.count(arr[i]))
            ans2+=cnt[i],book.insert(arr[i]);
    printf("%lld %lld\n",ans1,ans2);
    return 0;
}
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *