bzoj3193【JLOI2013】地形生成

bzoj3193【JLOI2013】地形生成

3193: [JLOI2013]地形生成

Time Limit:10 SecMemory Limit:128 MB
Submit:277Solved:135
[Submit][Status][Discuss]

Description

最近IK正在做關於地形建模的工作。其中一個工作階段就是把一些山排列成一行。每座山都有各不相同的標號和高度。為了遵從一些設計上的要求，每座山都設置了一個關鍵數字，要求對於每座山，比它高且排列在它前面的其它山的數目必須少於它的關鍵數字。 顯然滿足要求的排列會有很多個。對於每一個可能的排列，IK生成一個對應的標號序列和等高線序列。標號序列就是按順序寫下每座山的標號。等高線序列就是按順序寫下它們的高度。例如有兩座山，這兩座山的一個合法排列的第一座山的標號和高度為1和3，而第二座山的標號和高度分別為2和4，那麼這個排列的標號序列就是1 2，而等高線序列就是3 4. 現在問題就是，給出所有山的信息，IK希望知道一共有多少種不同的符合條件的標號序列和等高線序列。  

Input

輸入第一行給出山的個數N。接下來N行每行有兩個整數，按照標號從1到N的順序分別給出一座山的高度和關鍵數。  

Output

  輸出兩個用空格分隔開的數，第一個數是不同的標號序列的個數，第二個數是不同的等高線序列的個數。這兩個答案都應該對2011取模，即輸出兩個答案除以2011取余數的結果  

Sample Input

2
1 2
2 2

Sample Output

2 2

HINT

對於所有的數據，有1<=N<=1000，所有的數字都是不大於109的正整數。

第一問：可以發現對一座山有影響的只可能是比它高的山，所以我們可以將山按高度從大到小排序，依次插入每座山。對於高度相同的山一起處理，按關鍵值從小到大排序，然後將每座山能插入的位置數乘到答案中，即min(i,a[i].key+1)+num-1，num為它在高度相同的山中的排名。

第二問：為了不重復計算，我們每次將高度相同的山拿出來，然後讓插入之後的順序也不改變。這樣就可以DP計算，f[i][j]=f[i-1][0]+f[i-1][1]+……+f[i-1][j]，其實f數組還可以降到一維。注意每次計算時要將f數組清零。
 

#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 1005
#define mod 2011
using namespace std;
int n,ans1=1,ans2=1,f[maxn];
struct data{int h,k;}a[maxn];
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline bool cmp(data x,data y)
{
	return x.h==y.h?x.ky.h;
}
int main()
{
	int i,j;
	n=read();
	F(i,1,n) a[i].h=read(),a[i].k=read()-1;
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i=j)
	{
		memset(f,0,sizeof(f));
		f[0]=1;
		for(j=i;j<=n&&a[i].h==a[j].h;j++)
		{
			ans1=ans1*(min(i,a[j].k+1)+j-i)%mod;
			for(int k=1;k