免費餡餅 - 武林網

免費餡餅

2019-11-10 19:00:36

字體：大中小

來源：轉載

供稿：網友

PRoblem Description

都說天上不會掉餡餅，但有一天gameboy正走在回家的小徑上，忽然天上掉下大把大把的餡餅。說來gameboy的人品實在是太好了，這餡餅別處都不掉，就掉落在他身旁的10米范圍內。餡餅如果掉在了地上當然就不能吃了，所以gameboy馬上卸下身上的背包去接。但由于小徑兩側都不能站人，所以他只能在小徑上接。由于gameboy平時老呆在房間里玩游戲，雖然在游戲中是個身手敏捷的高手，但在現實中運動神經特別遲鈍，每秒種只有在移動不超過一米的范圍內接住墜落的餡餅。現在給這條小徑如圖標上坐標：

為了使問題簡化，假設在接下來的一段時間里，餡餅都掉落在0-10這11個位置。開始時gameboy站在5這個位置，因此在第一秒，他只能接到4,5,6這三個位置中期中一個位置上的餡餅。問gameboy最多可能接到多少個餡餅？（假設他的背包可以容納無窮多個餡餅）

Input

輸入數據有多組。每組數據的第一行為以正整數n(0 < n < 100000)，表示有n個餡餅掉在這條小徑上。在結下來的n行中，每行有兩個整數x,T(0 < T < 100000),表示在第T秒有一個餡餅掉在x點上。同一秒鐘在同一點上可能掉下多個餡餅。n=0時輸入結束。

Output

每一組輸入數據對應一行輸出。輸出一個整數m，表示gameboy最多可能接到m個餡餅。提示：本題的輸入數據量比較大，建議用scanf讀入，用cin可能會超時。

Example Input

65 14 16 17 27 28 30Example Output
4Hint
說實話，看了網上別人的解析后才有點明白，很瓜皮。原理是數塔模型。01 #include<stdio.h>
02 #include<string.h>
03 int a[100000][11];
04 int Max(int a, int b, int c)
05 {
06     int n;
07     n = a > b? a:b;
08     return n > c ? n : c;
09 }
10 int main()
11 {
12     int i, n, max, x, t;
13     while(scanf("%d", &n) != EOF)
14     {
15         if(n == 0) break;
16         max = 0;
17         memset(a, 0, sizeof(a));
18         for(i = 0; i < n; i++)
19         {
20             scanf("%d%d", &x, &t);
21             a[t][x] += 1;
22             if(t > max) max = t;
23         }
24         for(t = max - 1; t >= 0; t--)
25         {
26             a[t][0] += Max(0, a[t+1][0], a[t+1][1]);
27             for(x = 1; x < 10; x++)
28             {
29                 a[t][x] += Max(a[t+1][x-1], a[t+1][x], a[t+1][x+1]);
30             }
31             a[t][10] += Max(a[t+1][9], a[t+1][10], 0);
32         }
33         printf("%d/n", a[0][5]);
34     }
35     return 0;
36 }