NOIP2011提高組 選擇客棧 hotel 解題報告

【問題描述】 
麗江河邊有n 家很有特色的客棧，客棧按照其位置順序從1 到n 編號。每家客棧都按照某一種色調進行裝飾（總共k 種，用整數0 ~ k-1 表示），且每家客棧都設有一家咖啡店，每家咖啡店均有各自的最低消費。兩位遊客一起去麗江旅遊，他們喜歡相同的色調，又想嘗試兩個不同的客棧，因此決定分別住在色調相同的兩家客棧中。晚上，他們打算選擇一家咖啡店喝咖啡，要求咖啡店位於兩人住的兩家客棧之間（包括他們住的客棧），且咖啡店的最低消費不超過p。他們想知道總共有多少種選擇住宿的方案，保證晚上可以找到一家最低消費不超過p元的咖啡店小聚。

 【輸入】輸入文件hotel.in，共n+1 行。第一行三個整數n，k，p，每兩個整數之間用一個空格隔開，分別表示客棧的個數，色調的數目和能接受的最低消費的最高值；接下來的n 行，第i+1 行兩個整數，之間用一個空格隔開，分別表示i 號客棧的裝飾色調和i 號客棧的咖啡店的最低消費。

 【輸出】輸出文件名為hotel.out。輸出只有一行，一個整數，表示可選的住宿方案的總數。 

【輸入輸出樣例1】 
hotel.in 
5 2 3
 0 5 
1 3 
0 2 
1 4 
1 5 
hotel.out 

3 
【輸入輸出樣例說明】

客棧編號	①	②	③	④	⑤
色調	0	1	0	1	1
最低消費	5	3	2	4	5

2人要住同樣色調的客棧，所有可選的住宿方案包括：住客棧①③，②④，②⑤，④⑤，但是若選擇住4、5 號客棧的話，4、5 號客棧之間的咖啡店的最低消費是4，而兩人能承受的最低消費是3 元，所以不滿足要求。因此只有前3 種方案可選。 

【數據范圍】
 對於30%的數據，有n≤100； 
對於50%的數據，有n≤1,000； 
對於100%的數據，有2≤n≤200,000，0<k≤50，0≤p≤100， 0≤最低消費≤100。

【分析】
 記憶化枚舉，或者動態規劃。
可以邊讀入邊計算：
 Pre[i]：前i個客棧中，最後一個 消費小於P的客棧。
Sum[i,j]：前j個客棧中，第i種顔色的總數量。   
S：總方案數

定義ci,pi表示讀入時第i個客棧的顔色、價格。
Sum[ci,i]=Sum[ci,i-1]+1;
Sum[j,i]=Sum[j-1,i](j!=ci)
 
如果pi<=P，Pre[i]=Pre[i-1]+1，S+=Sum[ci][Pre[i]]-1。
如果pi>P，Pre[i]=Pre[i-1]，S+=Sum[ci][Pre[i]]。


最後輸出S即可。沒有必要使用long long類型。

時間複雜度：O（NK）
空間複雜度：NK


【我的代碼】

C++语言: Codee#24285

01 /*
02 *Problem:NOIP2011-Senior-Hotel
03 *Date:2011.11.27
04 *Author:Yee-fan Zhu
05 */
06 #include <cstdio>
07 #include <cstdlib>
08 #include <iostream>
09 using namespace std;
10
11 const int MAXN=200002;
12 int Sum[52][MAXN];
13 int Pre[MAXN];
14 int S=0;
15 int N,P,K;
16
17 void init()
18 {
19     std::ios::sync_with_stdio(false);
20     scanf("%d %d %d\n",&N,&K,&P);
21    
22     for (int i=0;i<=N;i++)
23         Pre[i]=0;
24     for (int i=0;i<=N;i++)
25         for (int j=0;j<=K;j++)
26             Sum[j][i]=0;
27    
28     int c,p;
29     for (int i=1;i<=N;i++)
30     {
31         scanf("%d %d\n",&c,&p);
32         Sum[c][i]=Sum[c][i-1]+1;
33        
34         for (int j=0;j<K;j++)
35             if(j!=c)
36                 Sum[j][i]=Sum[j][i-1];
37        
38         if(p<=P)
39         {
40             Pre[i]=i;
41             S+=Sum[c][Pre[i]]-1;
42         }
43         else
44         {
45             Pre[i]=Pre[i-1];
46             S+=Sum[c][Pre[i]];
47         }
48     }
49     printf("%d\n",S);
50 }
51
52 int main()
53 {
54     freopen("hotel.in","r",stdin);
55     freopen("hotel.out","w",stdout);
56     init();
57     return 0;
58 }

【評測結果】
正在连接评测机...

已连接到评测机

GRID	1
名称	Flitty
系统版本	1.00
备注	COGS 1号评测机 Flitty

正在编译...
编译成功

测试点	结果	得分	运行时间	内存使用	退出代码
1	正确	10	0.000 s	41681 KB	0
2	正确	10	0.000 s	41681 KB	0
3	正确	10	0.000 s	41681 KB	0
4	正确	10	0.001 s	41681 KB	0
5	正确	10	0.001 s	41681 KB	0
6	正确	10	0.001 s	41681 KB	0
7	正确	10	0.054 s	41681 KB	0
8	正确	10	0.125 s	41681 KB	0
9	正确	10	0.192 s	41681 KB	0
10	正确	10	0.190 s	41681 KB	0

运行完成
运行时间 0.564 s
平均内存使用 41681 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!
已完成数据库校验。