{"problem":{"name":"[ICPC 2020 Shanghai R] Fountains","description":{"content":"Suppose you and your teammate Mixsx will attend the Namomo Camp. The Namomo Camp will happen in $n$ consecutive days. We name the $i$-th day as day $i$ ($1\\le i\\le n$). The cost of day $i$ is $s_i$.  ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":6000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9824"},"statements":[{"statement_type":"Markdown","content":"Suppose you and your teammate Mixsx will attend the Namomo Camp. The Namomo Camp will happen in $n$ consecutive days. We name the $i$-th day as day $i$ ($1\\le i\\le n$). The cost of day $i$ is $s_i$. \n\nUnfortunately, the schedule of the Namomo Camp conflicts with Mixsx's final exams. Mixsx has final exams every day between day $L$ and day $R$. The exact value of $L$ and $R$ have not been announced by his college so we assume that every pair of integers $L$ and $R$ satisfying $1\\le L\\le R\\le n$ will be chosen with probability $1/(n(n+1)/2)$. He decides to take all the exams and thus be absent from the Namomo Camp from day $L$ to day $R$. His $\\textit{loss}$ will be $\\sum_{i=L}^R s_i$ in this case. \n\nAs Mixsx's teammate, you want Mixsx to give up his final exams and come back to the Namomo Camp. You can prepare $k$ plans before $L$ and $R$ are announced. In the $i$-th plan ($1\\le i\\le k$), you shut the electricity off to his college every day from day $l_i$ to day $r_i$. You can choose the values of $l_i$ and $r_i$ as long as they are two integers satisfying $1\\le l_i\\le r_i\\le n$.\n\nOnce $L$ and $R$ are announced, you can choose a plan $x$ ($1\\le x\\le k$) such that $L\\le l_x\\le r_x\\le R$. Then Mixsx will come back to the Namomo Camp on every day from day $l_x$ to day $r_x$. His loss becomes $\\sum_{i=L}^R s_i-\\sum_{i=l_x}^{r_x} s_i$ in this case. You will choose a plan that minimizes Mixsx's loss. If no plan $x$ satisfies $L\\le l_x\\le r_x\\le R$, Mixsx will attend his final exams normally and his loss is $\\sum_{i=L}^R s_i$.\n\nPlease calculate the minimum possible expected loss $ans_k$ of Mixsx if you choose the $k$ plans optimally. Output $ans_k\\cdot n(n+1)/2$ for every $k$ from $1$ to $n(n+1)/2$.\n\nFormally, given a list of $n$ numbers $s_i$ $(1 \\leq i \\leq n)$, define a loss function $C(L, R) = \\sum_{i=L}^R s_i$. Given an integer $k$ ($1 \\leq k \\leq n (n + 1) / 2$), you should select $2k$ integers $l_1, \\ldots, l_k, r_1,\\ldots, r_k$ satisfying $1\\le l_i\\le r_i\\le n$ for all $1 \\leq i \\leq k$, such that\n\n$$\\sum_{1\\leq L\\leq  R\\leq n} \\left[C(L, R) - \\max_{1\\le i\\le k, L \\leq l_i \\leq r_i \\leq R} C(l_i, r_i) \\right]$$\n\n is minimized. ($\\max_{1\\le i\\le k, L \\leq l_i \\leq r_i \\leq R} C(l_i, r_i)$ is defined as $0$ if no $i$ satisfies $1\\le i\\le k$ and $L \\leq l_i \\leq r_i \\leq R$.) Output the minimized value for every integer $k$ in $[1, n(n + 1) / 2]$. \n\n## Input\n\nThe first line contains an integer $n~(1 \\leq n \\leq 9)$. The second line contains $n$ space separated integers $s_i~(1 \\leq s_i \\leq 10^9)$.\n\n## Output\n\nThe output contains $n (n + 1) / 2$ integers in their own lines, the expectations when $k = 1, \\ldots, n (n + 1) / 2$ multiplied by $n (n + 1) / 2$. It can be shown that the results are always integers.\n\n[samples]\n\n## Note\n\nFor the first test case, we only need to consider the case $k = 1$. We can only choose $l_1=r_1=1$. Then the expected loss is $C(1, 1) - C(1, 1) = 0$ and the result is $0 \\times 1 \\times (2) / 2 = 0$.\n\nFor the third test case, consider the case when $k = 3$. We choose $l_1=r_1=1$, $l_2=r_2=3$ and $l_3=1, r_3=3$. The expected loss is $2$. And the result is $2 \\times 6 = 12$.","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9824","tags":["动态规划 DP","2020","上海","O2优化","ICPC"],"sample_group":[["1\n1","0"],["2\n13 24","26\n13\n0"],["3\n6 4 7","33\n21\n12\n8\n4\n0"]],"created_at":"2026-03-03 11:09:25"}}