题解：P3255 [JLOI2013] 地形生成
123456xwd
·
·
题解
设关键数字序列为 a。
先考虑第一问，若没有高度相同的山，那么是好做的，按照高度排序，答案为 \prod \min(a_i,i)，即放到一个山的后面或者放入最前面。
若有相同的，那么我们不妨在排序的时候按照 a_i 从小到大排，那么每个山还可以放到比他 a_i 小的相同高度的山后面（若那个山满足了限制，这个山也一定满足了）。
那么答案为 \prod \min(a_i+cnt,i)，其中的 cnt 表示在他前面且高度一样的点的数量。
考虑第二问，唯一不同的变为了高度一样的本质是一样的。
设当前有 m 个高度一样的，将其按照 a_i 从小到大标号，要依次放入 x 个栈中，且每个山放入的栈不能在上一个山放入栈的前面。
那么设 $dp_{i,j}$ 表示考虑了这 $m$ 个数的前第 $i$ 个，第 $i$ 个放入第 $j$ 个栈。
那么初始化 $dp_{1,j}=1$。
转移为 $dp_{i,j}=\sum_{k\le j}dp_{i-1,k}$，就是一个前缀和，可以降维优化到 $\mathcal{O}(n)$。
注意每个 $i$ 对应的合法的 $j$ 的范围不一样。
最后用乘法原理，把每一段最终的 $\sum_jdp_{m,j}$ 乘起来即可。
```c++
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define p_b push_back
#define m_p make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define ls k<<1
#define rs k<<1|1
#define mid ((l+r)>>1)
#define gcd __gcd
#define lowbit(x) (x&(-x))
using namespace std;
int rd(){
int x=0,f=1; char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if (ch=='-') f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
return x*f;
}
void write(int x){
if(x>9) write(x/10);
putchar('0'+x%10);
}
const int N=1005,mod=2011;
void add(int &x,int y){
x+=y;
if(x>=mod)x-=mod;
}
int dp[N],n,ans=1;
struct node{
int a,h;
friend bool operator< (const node &x,const node &y){return x.h!=y.h?x.h>y.h:x.a<y.a;}
}a[N];
int main(){
n=rd();
for(int i=1;i<=n;i++)a[i].h=rd(),a[i].a=rd();
sort(a+1,a+1+n);
for(int i=1,cnt=0;i<=n;i++){
if(a[i].h!=a[i-1].h) cnt=0;
else cnt++;
ans=ans*min(a[i].a+cnt,i)%mod;
}
printf("%d ",ans);ans=1;
for(int i=1,j;i<=n;i=j+1){
j=i;while(j<n&&a[j+1].h==a[i].h) j++;
memset(dp,0,sizeof(dp));
for(int k=1;k<=min(i,a[i].a);k++) dp[k]=1;
for(int l=i+1;l<=j;l++)for(int k=1;k<=min(i,a[l].a);k++) add(dp[k],dp[k-1]);
int res=0;for(int k=1;k<=min(i,a[j].a);k++) add(res,dp[k]);
ans=ans*res%mod;
}printf("%d\n",ans);
return 0;
}
```