NOIP2011 Day1 安排客栈

首先，对题目进行一个数学上的描述：
有color[],price[]两个数组，求满足条件
color[i] == color[j](i < j) 且 存在i<=k<=j满足price[k]<=limit(即题目描述中的p)
的的个数。

显然，如果使用最朴素的办法，可以用两个for嵌套，即：

for(i = 1;i <= n;i ++)
   for(j = i + 1;j <= n;j ++)
       if(check(i,j))  tot ++;

可是，题目中n的上限是200000。即使check可以在O(1)时间内完成，算法复杂度也是n^2的，所以我们需要一个更巧妙的方法：用空间换取时间。

具体思路是这样的。如果price[i]<=limit,那么j的取值就可以是i其后所有颜色与i相同的客栈，因此，我们需要一个数组cnt[i][k]来记录从第i个开始,颜色为k的客栈的数量（具体实现见代码）。 可是，如果price[i]>limit,那又会是什么情况呢？

这个时候，如果我们可以在i后面找到一个m满足price[m]<=limit,那么j可以取从m开始颜色和i相同的所有客栈编号（具体实现见代码）。由于i显然是递增的，因此不会出现重复计数的情况。至此，问题成功解决。
 

C语言: 高亮代码由发芽网提供

01 #include <stdio.h>
02 #include <stdlib.h>
03 #include <time.h>
04 #define MAX_HOTEL (200000 + 10)
05 #define MAX_COLOR (50 + 5)
06 #include <string.h>
07
08 long cnt[MAX_HOTEL][MAX_COLOR];
09 long next[MAX_HOTEL];
10 long n;
11 int k,limit;
12 int color[MAX_HOTEL];
13 int price[MAX_HOTEL];
14
15 int solve()
16 {
17     long i,j;
18     long long ans = 0;
19     scanf("%ld%d%d",&n,&k,&limit);
20     for(i = 0;i < n;i ++)
21         scanf("%d%d",&color[i],&price[i]);
22        
23     for(i = 0;i < k;i ++)
24         cnt[n][i] = 0;
25     for(i = n - 1;i >= 0;i --)
26     {
27         for(j = 0;j < k;j ++)
28             cnt[i][j] = cnt[i + 1][j];
29         cnt[i][color[i]] ++;
30     }
31    
32     next[n] = -1;  //-1表示不存在
33     for(i = n - 1;i >= 0;i --)
34     {
35         if(price[i] <= limit)
36             next[i] = i;
37         else    next[i] = next[i + 1];
38     }
39        
40     for(i = 0;i < n;i ++)
41     {
42         if(price[i] <= limit)    ans += cnt[i][color[i]] - 1;
43         else if(next[i] != -1)
44         {
45             ans += cnt[next[i]][color[i]];
46         }
47         else break;  //如果i后面已经没有price小于limit的客栈了，可以直接跳出。
48     }
49     printf("%lld\n",ans);
50     return 0;
51 }
52
53 void test()  //测试用
54 {
55     char input[1000];
56     char printstdans[1000];
57     clock_t start,end;
58     int i;
59     for(i = 1;i <= 10;i ++)
60     {
61         sprintf(input,"hotel%d.in",i);
62         sprintf(printstdans,"cat hotel%d.ans",i);
63         freopen(input,"r",stdin);
64         printf("%d:\n",i);
65         memset(next,0,sizeof(next));
66         memset(cnt,0,sizeof(cnt));
67         start = clock();
68         solve();
69         end = clock();
70         system(printstdans);
71         printf("%.2f secs\n",(float)(end - start) / CLOCKS_PER_SEC);
72     }
73 }
74
75 int main()
76 {
77     test();
78     return 0;
79 }

虽然本人在考场上头脑发热只得了40分，个人认为这道题还是很不错的，带有一点动态规划的味道。