题解：P3255 [JLOI2013] 地形生成

· · 题解

update：代码贴错了，已修改，现在的代码可以过题。

update：修改了一处假掉的地方，感谢 @Enoch006 指出。

有两问，第一问中高度相同编号不同的山看作不同，第二问中高度相同的山看作相同。

第一问

题目对山的限制在于“高于它且排在它前面”的数量，比它矮的山放在哪里对它是没有影响的。因此，对于两座高度不同的山，我们先插入高度大的，即按高度降序排序。 高度相同时，按照关键字从小到大排序。 对于这一问，高度相同的山怎么排其实是无所谓的，第二问中有影响，会说明（划掉的是错的，下面会说明）。

排完序之后只需要按顺序一个个插进去。设当前插入的山是 i（排序后的下标），前面有 p 座严格比它高的山，这座山的关键数字是 key，那么对于这座山，方案数就是 \min\{key,p\}+(i-p-1)+1=\min\{key+i,i\}。最后所有山乘起来就可以了。

上面划掉的地方就是假了的地方。原因在于，如果我们先插入限制松的，就会导致限制它的旁边放不了限制更紧的，但是我们仍然会把这个不合法的位置统计进去，这样乘法原理就不对了。

第二问

这一问中相同高度的不作区分。将相同高度的一起考虑，设高度严格大于它们的有 p 个。可以理解为，在 p+1 个空位中可重复地塞若干个相同小球，其中每个小球能塞的空位是一段给定的前缀。

设这些小球的选择分别是 t_1,t_2,\cdots,t_m，由于这些小球不作区分，我们钦定 t_1 \le t_2 \leq \cdots \leq t_n。考虑它们加入的顺序，能塞的前缀之间是包含关系，我们先插入限制紧的。因此，高度从大到小为第一关键字，关键数字从小到大为第二关键字。

排序完设 dp_{i,j} 表示现在插入了前 i 个，第 i 个插入的空挡位置（总共有 p+1 个空位） 是 j 的方案数。 由于 t_{i-1} \leq t_i，所以，dp_{i,j}=sum_{i-1,j},j \in [1,\min(p,a[i].se)+1]。

最后答案为每种高度的方案数相乘。

代码

#include<bits/stdc++.h>
#define Spc putchar(' ')
#define End putchar('\n')
#define For(i,il,ir) for(int i=(il);i<=(ir);++i)
#define Fr(i,il,ir) for(int i=(il);i<(ir);++i)
#define Forr(i,ir,il) for(int i=(ir);i>=(il);--i)
#define ForE(u) for(int i=head[u];~i;i=e[i].nxt)
#define fi first
#define se second
#define mk make_pair
#define pb emplace_back
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
namespace _OvO_{
    template<typename T>
    inline void rd(T& x){
        bool f=0;x=0;char ch=getchar();
        while(ch<'0'||ch>'9'){ if(ch=='-') f=1; ch=getchar(); }
        while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
        if(f) x=-x;
    }
    template<typename T,typename... Args>
    void rd(T& first,Args&... args){ rd(first),rd(args...); }
    int write_num[50];
    inline void write(ll x){
        int len=0;
        if(x<0) putchar('-'),x=-x;
        do write_num[len++]=x%10ll; while(x/=10ll);
        while(len--) putchar(write_num[len]+'0');
    }
}using namespace _OvO_;
const int maxn=1005;
const ll mod=2011;

int n,p;
pii a[maxn];
ll f[maxn][maxn],sum[maxn],ans;

void solve1(){
    p=0,ans=1ll;
    For(i,1,n){
        while(a[p+1].fi>a[i].fi) p++;
        ans=ans*(min(a[i].se,p)+i-p)%mod;
    }write(ans);
}
void solve2()
{
    p=0,ans=1ll;
    f[0][1]=1;
    For(i,1,n){
        while(a[p+1].fi>a[i].fi) p++;
        For(j,1,n+1) sum[j]=(sum[j-1]+f[i-1][j])%mod;
        if(p==i-1){
            ans=ans*sum[n+1]%mod;
            For(j,1,n+1) f[i-1][j]=(j==1),sum[j]=1ll;
        }
        For(j,1,min(p,a[i].se)+1) f[i][j]=sum[j];
        For(j,min(p,a[i].se)+2,n+1) f[i][j]=0;
    }
    For(j,1,n+1) sum[j]=(sum[j-1]+f[n][j])%mod;
    write(ans*sum[n+1]%mod);
}
signed main()
{
    rd(n); For(i,1,n) rd(a[i].fi,a[i].se),a[i].se--;
    sort(a+1,a+1+n,[&](pii xx,pii yy){ return xx.fi==yy.fi?xx.se<yy.se:xx.fi>yy.fi; });
    solve1();Spc;solve2();End; return 0;
}