传送门

快合格考了发现自己啥都不会没啥希望过，于是又回来刷题了。。。

这个$DP$很有意思。

第一问就是个套路$DP$，按高度降序排序，依次把山插进去。因为题目要求的是严格大于，排序时高度相同的按关键值降序排序就好了。

第二问一开始想了个$O(n)$的假做法，显然数据范围是要$O(n^2)$的。。。

好难啊不会了告辞

还是排好序，我们考虑把相同高度的山一块插进去。对于每一段相同高度的区间$[l,r]$设$f(i,j)$为这段区间中前$i$座山，插进所有山中前$j$座山的前面的方案数。

每座山要么插到第$j$座山前面（$j\le $关键值），有$f(i-1,j)$种方案；要么插到前$j-1$座山前面，有$f(i,j-1)$种方案。

也就是$f(i,j)=f(i,j-1)+f(i-1,j)$。

因为相同高度的山是单独考虑的，根据乘法原理答案为所有$f(r-l+1,min\{l,H[r].cnt\})$的乘积。

$f$要滚起来，要不然清空太慢。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <stack>

#define maxn 1005
#define inf 0x3f3f3f3f

const int mod = 2011;

using namespace std;

inline int read(){
    int x=0,y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
struct hill{
    int h,cnt;
    bool operator < (const hill &x)const{
        if(h!=x.h)return h>x.h;
        return cnt<x.cnt;
    }
}H[maxn];
int f[2][maxn];
int main(){
    int n=read(),ans=1,sum1=0,sum2=0,p;
    for(register int i=1;i<=n;++i)H[i].h=read(),H[i].cnt=read();
    sort(H+1,H+1+n);
    for(register int i=2;i<=n;++i){
        if(H[i].h==H[i-1].h)++sum1;
        else sum2=i-1,sum1=0;
        ans=1ll*ans*(min(H[i].cnt-1,sum2)+sum1+1)%mod;
    }
    printf("%d ",ans);
    ans=1;
    for(register int i=1;i<=n;i=p+1){
        memset(f,0,sizeof f);
        p=i+1;
        while(p<=n&&H[p].h==H[i].h)++p;
        --p;
        for(register int j=1;j<=i;++j)f[0][j]=1;
        for(register int j=i;j<=p;++j)
            for(register int k=1;k<=i;++k){
                f[j-i+1&1][k]=f[j-i+1&1][k-1];
                if(k<=H[j].cnt)(f[j-i+1&1][k]+=f[j-i&1][k])%=mod;
            }
        ans=1ll*ans*f[p-i+1&1][min(i,H[p].cnt)]%mod;
    }
    printf("%d\n",ans);
}