3193

首先按照第一關鍵字高度倒敘，第二關鍵字順序的順序拍下序

第一問O(n) dp一下

考慮一下第i個山能放在哪些山的后面，對于比第i個山高的，只能放在前關鍵字個的后面，但排在他的前面的和他一樣高的的后面都可以放，因為他的關鍵字比已放的大

第二問大概就不能O(n)了...

我們強制讓一樣高的關鍵字從小到大排列。如果\(d[i]\)表示當前一個放在第 i個比他們高的后面，可以從\(i\in[0,i-1]\)轉移過來

---

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>using namespace std;
const int P = 2011;
const int M = 1101;
int res=1,n,m,k,sum,f[M],d[M];struct vv
{int x,y;
}a[M];
bool cmp(vv a,vv b) { return a.x!=b.x ? a.x>b.x: a.y<b.y; } int main()
{scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);sort(a+1,a+1+n,cmp);for(int i=1;i<=n;i++){if(a[i].x!=a[i-1].x) {sum+=k;k=0;}res=res*(min(a[i].y,sum+1)+k)%P;k++;}printf("%d ",res);sum=0; res=1;for(int i=1;i<=n;){int z=i;while(a[i].x==a[z].x) z++;memset(d,0,sizeof(d));d[0]=1;for(int j=i;j<z;j++){f[0]=1;for(int l=1;l<=sum;l++) f[l]=(f[l-1]+d[l])%P;for(int l=1;l<a[j].y;l++) d[l]=(d[l]+f[l-1])%P;}int k=0;for(int j=0;j<=sum;j++) k+=d[j];k%=P; sum+=z-i; i=z;res=res*k%P;}printf("%d",res);
}

轉載于:https://www.cnblogs.com/ZUTTER/p/11095129.html

總結

以上是生活随笔為你收集整理的[JLOI2013]地形生成的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。