P10592题解

· · 题解

看见各位大神都是直接给的思路，本蒟蒻就奉上自己的解题过程吧。

第一步：暴力 dfs

看了看题，发现题意是若序列不是不下降子序列，则从中删除一个数，问一共有多少种删法，哎呀，没思路，算了，先打 dfs 找找规律吧。于是就有了如下代码。

//朴素的暴力
#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[2010],vis[2010];
int ans,n,mod=1e9+7;
void dfs(int u)
{
    int last=-1,flag=1;
    for(int i=1;i<=n;i++)
    {
        if(vis[i]==0)
        {
            if(a[i]<last) flag=0;//如果剩下的数不是不下降子序列，则flag=0。
            last=a[i];
        }
    }
    if(flag==1)
    {
        ans=(ans+1)%mod;//如果是不下降子序列的话，统计答案
        return;
    }
    for(int i=1;i<=n;i++)//枚举删哪些数
    {
        if(vis[i]==0)
        {
            vis[i]=1;//删掉他的话标记为1
            dfs(u+1);
            vis[i]=0;//回溯
        }
    }
}
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];//输入
    dfs(1);
    cout<<ans;
    return 0;
}

第二步：暴力 dp

不难发现这道题应该和数学有关， dp_{i,j} 表示以 i 为结尾，长度为 j 的不下降子序列。转移方程为：

dp_{i,j}=\sum_{k=1}^{k<i且a_k\le a_i}dp_{k,j-1}。

那么 ans 又该如何统计呢。先默认所有的数都只能删到只剩这一个数，所以 ans 赋初始值为 n\times A_{n-1}^{n-1}（剩下 n-1 个数有 A_{n-1}^{n-1} 种删法）然后一边计算 dp_{i,j} 一边统计ans，ans每次减少：

dp_{i,j}\times (len-1)\times A_{n-len}^{n-len}

（表示每一种以 i 结尾长度为 j 的不下降子序列里的每一个长度为 (n-1) 的不下降子序列都会因为这个子序列而惨遭减去 A_{n-len}^{n-len} 种情况，就像我的零花钱一样，但是因为留下这个序列也算一种方法，所以还要再加上 A_{n-len}^{n-len} 种，总结下来就是如上公式），累死我了，下奉上代码。

#include<bits/stdc++.h>
using namespace std;
#define int long long//好用，多用
int a[2010],dp[2010][2010];
int ans,n,mod=1e9+7,cnt;
int ff(int x)
{
    int ret=1;
    for(int i=1;i<=x;i++) ret=(ret*i)%mod;
    return ret;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);//关同步流
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        dp[i][1]=1;
    }
    ans=(n*ff(n-1))%mod;//初始化
    for(int i=1;i<=n;i++)
    {
        for(int len=2;len<=i;len++)
        {
            for(int j=1;j<i;j++)
            {
                if(a[j]<=a[i])
                {
                    dp[i][len]+=dp[j][len-1];//dp转移方程
                }
            }
            ans=(ans-(dp[i][len]*(len-1)%mod)*ff(n-len)+mod*mod)%mod;//如上公式
        }
    }
    cout<<ans;
    return 0;
}

复杂度 O(n^3)。

第三步：树状数组优化dp

很明显上面的代码还有优化的空间，a_j\le a_i 这一步可以使用树状数组优化，只需要让树状数组以 a_i 为下标，然后每次调用 query(a[i])。这里还有一个问题，len 这一维要倒序循环，并且调用 query 和 add 函数时只用遍历 i 这一维，大家可以自行思考一下这是为什么。下面上代码。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[2010],lsh[2010],dp[2010][2010],k[2010],sum[2010][2010];
int ans,n,mod=1e9+7,cnt,maxx;
int ff(int x)
{
    int ret=1;
    for(int i=1;i<=x;i++) ret=(ret*i)%mod;
    return ret;
}
int lowbit(int x)
{
    return x&(-x);
}
void add(int x,int y,int k)
{
    for(int i=x;i<=n;i+=lowbit(i))
    {
        sum[i][y]=(k+sum[i][y])%mod;
    }
}
int query(int x,int y)
{
    int ret=0;
    for(int i=x;i;i-=lowbit(i))
    {
        ret=(ret+sum[i][y])%mod;
    }
    return ret;
}
signed main()
{
    cin>>n;
    int flag=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        lsh[i]=a[i];
        if(a[i]<a[i-1] && i!=1) flag=1;
    }
    if(flag==0)
    {
        cout<<1;
        return 0;
    }
    sort(lsh+1,lsh+n+1);
    int cnt=unique(lsh+1,lsh+1+n)-lsh-1;
    for(int i=1;i<=n;i++)
    {
        a[i]=lower_bound(lsh+1,lsh+1+cnt,a[i])-lsh;
        maxx=max(maxx,a[i]);
    }
    for(int i=1;i<=n;i++) k[i]=ff(i);
    for(int i=1;i<=n;i++)
    {
        ans=(ans+ff(n-1))%mod;
        for(int len=i;len>=2;len--)
        {
            int tot=query(a[i],len-1);
            add(a[i],len,tot);
            if(tot>0)
            {
                ans=(ans-(tot*(len-1)%mod)*k[n-len]%mod+mod*mod)%mod;
            }
        }
        add(a[i],1,1);
    }
    cout<<ans;
    return 0;
}

时间复杂度 O(n^2*log_2n)，完美AC。