程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> bzoj3193【JLOI2013】地形生成

bzoj3193【JLOI2013】地形生成

編輯:關於C++

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

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved