PRoblem Description

Input

Output

Example Input

65 14 16 17 27 28 30
Example Output
4
Hint
說實話，看了網上別人的解析后才有點明白，很瓜皮。原理是數塔模型。
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
}