[JOI Open 2016] 摩天大楼 / Skyscraper

Luogu
IDLGP9197
Time2000ms
Memory512MB
DifficultyP6
动态规划 DP2016JOI(日本)
将互不相同的 $N$ 个整数 $A_1, A_2, \cdots, A_N$ 按照一定顺序排列。 假设排列为 $f_1, f_2, \cdots, f_N$,要求:$| f_1 - f_2| + | f_2 - f_3| + \cdots + | f_{N-1} - f_N| \leq L$。 求满足题意的排列的方案数对 $10^9+7$ 取模后的结果。 ## Input 输入共两行。 第一行有两个整数 $N, L$。 第二行有 $N$ 个整数 $A_1, A_2, \cdots, A_N$。 ## Output 输出共一行一个整数,表示方案数对 $10^9+7$ 取模后的结果。 [samples] ## Background **译自 [JOI Open 2016](https://contests.ioi-jp.org/open-2016/index.html) T3 「高層ビル街 / Skyscraper」** ## Note ### 样例 1 解释 满足条件的六种方案分别为: $$ \begin{matrix} 2\ 3\ 6\ 9,& |2 - 3| + |3 - 6| + |6 - 9| &=& 7 \\ 2\ 3\ 9\ 6,& |2 - 3| + |3 - 9| + |9 - 6| &=& 10 \\ 3\ 2\ 6\ 9,& |3 - 2| + |2 - 6| + |6 - 9| &=& 8 \\ 6\ 9\ 3\ 2,& |6 - 9| + |9 - 3| + |3 - 2| &=& 10 \\ 9\ 6\ 2\ 3,& |9 - 6| + |6 - 2| + |2 - 3| &=& 8 \\ 9\ 6\ 3\ 2,& |9 - 6| + |6 - 3| + |3 - 2| &=& 7 \\ \end{matrix} $$ ### 数据规模与约定 **本题采用捆绑测试。** 对于所有数据,$1\le N\le 100$,$1\le L\le 1000$,$1\le A_i\le 1000$。 - Subtask 1(5 points):$N\le 8$。 - Subtask 2(15 points):$N\le 14$,$L\le 100$。 - Subtask 3(80 points):没有额外限制。
Samples
Input #1
4 10
3 6 2 9
Output #1
6
Input #2
8 35
3 7 1 5 10 2 11 6
Output #2
31384
API Response (JSON)
{
  "problem": {
    "name": "[JOI Open 2016] 摩天大楼 / Skyscraper",
    "description": {
      "content": "将互不相同的 $N$ 个整数 $A_1, A_2, \\cdots, A_N$ 按照一定顺序排列。 假设排列为 $f_1, f_2, \\cdots, f_N$,要求:$| f_1 - f_2| + | f_2 - f_3| + \\cdots + | f_{N-1} - f_N| \\leq L$。 求满足题意的排列的方案数对 $10^9+7$ 取模后的结果。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9197"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "将互不相同的 $N$ 个整数 $A_1, A_2, \\cdots, A_N$ 按照一定顺序排列。\n\n假设排列为 $f_1, f_2, \\cdots, f_N$,要求:$| f_1 - f_2| + | f_2 - f_3| + \\cdots + | f_{N-1} - f_N| \\leq L$。\n\n求满足题意的排列的方案数对 $10^9+7$ 取模后的结果。\n\n## Input\n\n输入共两行。\n\n...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments