P4609题解

· · 题解

P4609 [FJOI2016] 建筑师

外训听完组合数学后题单里的，但觉得 dp 能过，写完真过了。结果一看提交记录，荣获最劣解。再一看题解，怎么都是斯特林数，蒟蒻不会，于是写篇题解

首先，由于要求前后缀最大值的个数，所以我们考虑将数字从大到小插入

记 dp_{i,j,k} 为已经放了前 i 大的数，前后缀最大值分别为 j,k 的答案。

考虑将下一个数，即当前最大值插入对答案的影响。若放在两边，答案不变，前后缀最大值长度增加。若插在中间，由于已插入的数都比当前数大，不会对前后缀最大值产生影响，所以可以随便插，答案乘上 i-2

dp_{i,j,k}=dp_{i-1,j-1,k}+dp_{i-1,j,k-1}+(i-2)\times dp_{i-1,j,k}

初值为 dp_{1,1,1}=1

复杂度 O(nAB) 最大约 5\times 10^8 但常数小，可以通过

但当你兴冲冲写完一交，满屏的 MLE 发现空间也是 O(nAB) 的，所以考虑将第一维滚掉

所以我们先将询问离线，按照 n 从小到大排序，然后一边跑 dp，一边记录答案

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,M=1e9+7;
int n,A,B,dp[2][110][110],ans[N];
struct que{
    int n,a,b,id;
}q[N];
bool cmp(que x,que y){return x.n<y.n;}
signed main(){
    int T;
    cin>>T;
    for(int i=1;i<=T;i++){
        cin>>q[i].n>>q[i].a>>q[i].b;
        q[i].id=i;
    }
    sort(q+1,q+T+1,cmp);
    int l=1;
    while(q[l].n==1 and l<=T){ans[q[l].id]=((q[l].a==1)and(q[l].b==1));l++;}
    dp[0][1][2]=dp[0][2][1]=1;
    while(q[l].n==2 and l<=T){ans[q[l].id]=dp[0][q[l].a][q[l].b];l++;}
    for(int i=3;i<=q[T].n;i++){
        for(int j=1;j<=min(i,100);j++){
            for(int k=1;k<=min(i,100);k++){
                dp[i&1][j][k]=(dp[i&1^1][j-1][k]+dp[i&1^1][j][k-1]+1ll*dp[i&1^1][j][k]*(i-2))%M;    
            }
        }
        while(q[l].n==i and l<=T){ans[q[l].id]=dp[i&1][q[l].a][q[l].b];l++;}    
    }   
    for(int i=1;i<=T;i++)cout<<ans[i]<<'\n';
    return 0;
}

注意 n 只有 5\times 10^4，但 T 有 2\times 10^5，不要开小数组