TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P4712
  • 問題
  • P4712收集宝石
    制限 : 時間制限 : 10000 MS   メモリ制限 : 100000 KB
    審判説明 : 1s,96m
    問題説明

    何老板最近在玩一款收集宝石的手游。游戏虽然简单,但他仍然乐此不疲。
    游戏中,有30001个小岛排成一条直线,小岛从左往右编号0到30000,相邻岛屿间距为1。
    有n块宝石分布在这些岛上,其中第i块宝石分布在Pi号岛上。
    游戏规则如下:
    游戏开始时,游戏角色小飞侠位于0号小岛。何老板操控小飞侠往右飞行。
    第1次飞行距离只能是d米。也就是第一次飞行只能飞到d号小岛去着陆。
    第i(i>1)次飞行的距离可从Len-1, Len, Len+1中任选一个。Len是第i-1次飞行的距离。
    如果没法继续往右飞行了,游戏结束。
    每着陆到一个岛上,小飞侠就可以收集该岛上的所有宝石。何老板想知道,他最多能获得多少块宝石。

    入力形式

    第一行,两个整数n和d        1 ≤ n, d ≤ 30000
    接下来n行,每行一个整数,其中第i行表示第i块宝石所在的小岛的编号Pi。
    1 ≤ i ≤ n
    d ≤ P1 ≤ P2 ≤ ... ≤ Pn ≤ 30000

    出力形式

    一个整数,表示何老板最多能够收集到的宝石数量

    サンプル入力 1

    4 10
    10
    21
    27
    27

    サンプル出力 1

    3

    サンプル入力 2

    8 8
    9
    19
    28
    36
    45
    55
    66
    78

    サンプル出力 2

    6

    サンプル入力 3

    13 7
    8
    8
    9
    16
    17
    17
    18
    21
    23
    24
    24
    26
    30

    サンプル出力 3

    4

    サンプル入力 4

    11 15
    15
    18
    19
    19
    21
    23
    24
    26
    26
    29
    30

    サンプル出力 4

    2

    ヒント

    样例1说明
    飞行路线 0  →  10 (+1 宝石)  →  19  →  27 (+2 宝石)  → ...
    样例3说明
    飞行路线 0  →  7  →  13  →  18 (+1 宝石)  →  24 (+2 宝石)  →  30 (+1 宝石)  → ...

    数据范围

    对于40%的数据: 1 ≤ n, d ≤ 1000
    对于100%的数据: 1 ≤ n, d ≤ 30000


    ソース  codeforces 505C