很难的一道题
首先第一问,如果没有高度相同的,因为只有比他高的会产生影响,所以降序排序,然后从大往小往里插入,那么可插入的位置的个数就是min(i,key),然后我们考虑有重复的,若不考虑之前已经插入过的相同高度的,方案数仍然是min(i,key),那么现在矛盾的就是,新插入的关键字和之前的关键字的关系不知道,也就是说,不知道这个新的点,和之前相同高度的点的位置关系;可以按关键字升序排序,那么显然,如果两个高度相同的山挨着,那么后插入的一定能放在之前插入的后面,那么新增的位置就是之前的相同高度的个数(可能会觉得没考虑放在插入在相同高度的前面的情况,其实这种情况已经被直接放在不同高度的点后面包含了)
然后第二问,是一个之前没有做过的分段DP;
高度相同度互换位置是没有贡献的,可以把关键之大的强制放在小的后面,这样也能保证合法性;然后f[i][j]就是表示,放到第i个高度相同的点,位置在j,然后之前的点都在j之前方案数,那么显然f[i][j]+=f[i-1][k](1<=k<=g[i].key),那么在最后取答案的时候,就是取
f[r][min(l,max(g[i].key))]; (s为相同高度区间的右端点,l是做端点)
Code
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include <cmath> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <iostream> 6 #include <algorithm> 7 # define mod 2011 8 using namespace std; 9 typedef long long LL; 10 LL ans1,ans2; 11 int n; 12 struct MT{ 13 int h,key; 14 }g[1010]; 15 bool cmp(const MT a,const MT b){ 16 if(a.h==b.h) return a.key<b.key; 17 return a.h>b.h; 18 } 19 void init(){ 20 scanf("%d",&n); 21 for(int i=1;i<=n;i++) scanf("%d%d",&g[i].h,&g[i].key); 22 sort(g+1,g+n+1,cmp); 23 24 /* 25 cout<<"check::"<<endl; 26 for(int i=1;i<=n;i++){ 27 cout<<"i= "<<i<<" "<<g[i].h<<" "<<g[i].key<<endl; 28 } 29 cout<<"end"<<endl<<endl; 30 */ 31 } 32 void work1(){ 33 int ji=0,l; 34 ans1=1; 35 for(int i=1;i<=n;i++){ 36 if(g[i].h!=g[i-1].h){ 37 ji=0; l=i; 38 } 39 else{ 40 ji++; 41 } 42 ans1=ans1*(min(g[i].key,l)+ji)%mod; 43 // cout<<"i== "<<i<<" "<<min(g[i].key,l)+ji<<" "<<ji<<" "<<ans1<<endl; 44 } 45 cout<<ans1<<" "; 46 } 47 LL f[1010][1010]; 48 void work2(){ 49 int ji,l,mx,lim; 50 ans2=1; 51 bool flag; 52 for(int i=1;i<=n;i++){ 53 // cout<<"i= "<<i<<endl; 54 flag=1; 55 if(g[i].h!=g[i-1].h){ 56 ji=1; flag=0; mx=g[i].key; l=i; 57 lim=min(l,g[i].key); 58 for(int j=1;j<=lim;j++) f[i][j]=1; 59 } 60 else{ 61 ji++; mx=max(mx,g[i].key); 62 } 63 if(flag){ 64 lim=min(l,g[i].key); 65 for(int j=1;j<=mx;j++){ 66 f[i][j]=f[i-1][j]; 67 } 68 } 69 /* 70 if(i==7){ 71 cout<<"mx==" <<mx<<endl; 72 } 73 */ 74 for(int j=1;j<=1000;j++){ 75 f[i][j]=(f[i][j]+f[i][j-1])%mod; 76 } 77 // cout<<"everytime== "<<i<<" "<<f[i][min(g[i].key,l)]<<endl; 78 if(g[i].h!=g[i+1].h){ 79 // cout<<" i= "<<i<<endl; 80 // cout<<" min= "<<min(mx,l)<<" f== "<<f[i][min(mx,l)]<<endl; 81 82 ans2*=f[i][min(mx,l)]; 83 ans2%=mod; 84 } 85 } 86 cout<<ans2<<endl; 87 } 88 int main(){ 89 // freopen("a.in","r",stdin); 90 init(); 91 work1(); 92 work2(); 93 }