BZOJ2720 [Violet 5] 列队春游

Luogu

IDLGP10668

Time1000ms

Memory512MB

DifficultyP4

O2优化期望

给定正整数数列 $h_1,h_2,\cdots,h_n$。设 $p$ 为 $1\sim n$ 的随机排列。定义 $h'_i=h_{p_i}$。定义 $\mathrm{pre}_i$ 为最大的 $j\lt i$ 满足 $h'_j\ge h'_i$（如果不存在，规定为 $0$）。求出 $\displaystyle \sum_{i=1}^n (i-\mathrm{pre}_i)$ 的期望值，保留两位小数输出。 ## Input 第一行一个正整数 $n$，表示数列长度。第二行 $n$ 个正整数 $h_i$。 ## Output 输出一行一个实数，表示答案，保留两位小数。 [samples] ## Note 对于 $20\%$ 的数据，$1\leq n\leq 10$；对于 $50\%$ 的数据，$1\leq n\leq 70$，且 $h_i$ 互不相同；对于 $100\%$ 的数据，保证 $1\leq n\leq 300$，$1\leq h_i\leq 1000$。

Samples

Input #1

3
3 2 1

Output #1

4.33

API Response (JSON)

{
  "problem": {
    "name": "BZOJ2720 [Violet 5] 列队春游",
    "description": {
      "content": "给定正整数数列 $h_1,h_2,\\cdots,h_n$。设 $p$ 为 $1\\sim n$ 的随机排列。 定义 $h'_i=h_{p_i}$。定义 $\\mathrm{pre}_i$ 为最大的 $j\\lt i$ 满足 $h'_j\\ge h'_i$（如果不存在，规定为 $0$）。 求出 $\\displaystyle \\sum_{i=1}^n (i-\\mathrm{pre}_i)$ 的期望值，保留",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10668"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定正整数数列 $h_1,h_2,\\cdots,h_n$。设 $p$ 为 $1\\sim n$ 的随机排列。\n\n定义 $h'_i=h_{p_i}$。定义 $\\mathrm{pre}_i$ 为最大的 $j\\lt i$ 满足 $h'_j\\ge h'_i$（如果不存在，规定为 $0$）。\n\n求出 $\\displaystyle \\sum_{i=1}^n (i-\\mathrm{pre}_i)$ 的期望值，保留...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments