{"problem":{"name":"C. Hills","description":{"content":"Welcome to Innopolis city. Throughout the whole year, Innopolis citizens suffer from everlasting city construction. From the window in your room, you see the sequence of _n_ hills, where _i_\\-th of t","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF1012C"},"statements":[{"statement_type":"Markdown","content":"Welcome to Innopolis city. Throughout the whole year, Innopolis citizens suffer from everlasting city construction.\n\nFrom the window in your room, you see the sequence of _n_ hills, where _i_\\-th of them has height _a__i_. The Innopolis administration wants to build some houses on the hills. However, for the sake of city appearance, a house can be only built on the hill, which is strictly higher than neighbouring hills (if they are present). For example, if the sequence of heights is 5, 4, 6, 2, then houses could be built on hills with heights 5 and 6 only.\n\nThe Innopolis administration has an excavator, that can decrease the height of an arbitrary hill by one in one hour. The excavator can only work on one hill at a time. It is allowed to decrease hills up to zero height, or even to negative values. Increasing height of any hill is impossible. The city administration wants to build _k_ houses, so there must be at least _k_ hills that satisfy the condition above. What is the minimum time required to adjust the hills to achieve the administration's plan?\n\nHowever, the exact value of _k_ is not yet determined, so could you please calculate answers for all _k_ in range ? Here denotes _n_ divided by two, rounded up.\n\n## Input\n\nThe first line of input contains the only integer _n_ (1 ≤ _n_ ≤ 5000)—the number of the hills in the sequence.\n\nSecond line contains _n_ integers _a__i_ (1 ≤ _a__i_ ≤ 100 000)—the heights of the hills in the sequence.\n\n## Output\n\nPrint exactly numbers separated by spaces. The _i_\\-th printed number should be equal to the minimum number of hours required to level hills so it becomes possible to build _i_ houses.\n\n[samples]\n\n## Note\n\nIn the first example, to get at least one hill suitable for construction, one can decrease the second hill by one in one hour, then the sequence of heights becomes 1, 0, 1, 1, 1 and the first hill becomes suitable for construction.\n\nIn the first example, to get at least two or at least three suitable hills, one can decrease the second and the fourth hills, then the sequence of heights becomes 1, 0, 1, 0, 1, and hills 1, 3, 5 become suitable for construction.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"欢迎来到因诺波利斯市。全年，因诺波利斯市民都饱受持续的城市建设之苦。\n\n从你房间的窗户望出去，可以看到一排 #cf_span[n] 座山丘，其中第 #cf_span[i] 座山丘的高度为 #cf_span[ai]。因诺波利斯市政府计划在一些山丘上建造房屋。然而，为了城市美观，房屋只能建在严格高于相邻山丘（如果存在）的山丘上。例如，若高度序列为 #cf_span[5, 4, 6, 2]，则房屋只能建在高度为 #cf_span[5] 和 #cf_span[6] 的山丘上。\n\n市政府拥有一台挖掘机，可以在一小时内将任意一座山丘的高度降低一单位。挖掘机一次只能工作于一座山丘。允许将山丘高度降低至零甚至负值，但不允许增加任何山丘的高度。市政府希望建造 #cf_span[k] 座房屋，因此至少需要 #cf_span[k] 座满足上述条件的山丘。请问，调整山丘高度以实现该计划所需的最少时间是多少？\n\n然而，#cf_span[k] 的确切值尚未确定，因此请你计算所有 #cf_span[k] 在范围  内的答案。这里  表示 #cf_span[n] 除以二后向上取整。\n\n输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 5000]) —— 山丘序列的数量。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[ai] (#cf_span[1 ≤ ai ≤ 100 000]) —— 山丘的高度序列。\n\n请输出恰好  个用空格分隔的数字。第 #cf_span[i] 个输出的数字应等于使山丘高度调整后能建造 #cf_span[i] 座房屋所需的最少小时数。\n\n在第一个例子中，为了获得至少一座适合建造的山丘，可以将第二座山丘降低一单位（耗时一小时），此时高度序列变为 #cf_span[1, 0, 1, 1, 1]，第一座山丘变得适合建造。\n\n在第一个例子中，为了获得至少两座或三座适合建造的山丘，可以将第二座和第四座山丘降低，此时高度序列变为 #cf_span[1, 0, 1, 0, 1]，第 #cf_span[1, 3, 5] 座山丘变得适合建造。\n\n## Input\n\n输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 5000]) —— 山丘序列的数量。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[ai] (#cf_span[1 ≤ ai ≤ 100 000]) —— 山丘的高度序列。\n\n## Output\n\n请输出恰好  个用空格分隔的数字。第 #cf_span[i] 个输出的数字应等于使山丘高度调整后能建造 #cf_span[i] 座房屋所需的最少小时数。\n\n[samples]\n\n## Note\n\n在第一个例子中，为了获得至少一座适合建造的山丘，可以将第二座山丘降低一单位（耗时一小时），此时高度序列变为 #cf_span[1, 0, 1, 1, 1]，第一座山丘变得适合建造。\n\n在第一个例子中，为了获得至少两座或三座适合建造的山丘，可以将第二座和第四座山丘降低，此时高度序列变为 #cf_span[1, 0, 1, 0, 1]，第 #cf_span[1, 3, 5] 座山丘变得适合建造。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of hills.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of positive integers representing the initial heights of the hills.  \nLet $ m = \\left\\lceil \\frac{n}{2} \\right\\rceil $.  \n\nA hill at position $ i $ (where $ 1 \\leq i \\leq n $) is *suitable* for building a house if:  \n- $ a_i > a_{i-1} $ (if $ i > 1 $), and  \n- $ a_i > a_{i+1} $ (if $ i < n $).  \n\nWe may only *decrease* any $ a_i $ by any non-negative integer amount (each unit decrease costs 1 hour).  \n\nLet $ x_i \\in \\mathbb{Z}_{\\geq 0} $ denote the amount by which hill $ i $ is decreased, so the final height is $ a_i - x_i $.  \n\nLet $ S \\subseteq \\{1, 2, \\dots, n\\} $ be the set of positions where houses are built (i.e., suitable hills).  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 5000 $  \n2. $ 1 \\leq a_i \\leq 100{,}000 $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. For each $ i \\in S $:  \n   - If $ i > 1 $, then $ a_i - x_i > a_{i-1} - x_{i-1} $  \n   - If $ i < n $, then $ a_i - x_i > a_{i+1} - x_{i+1} $  \n4. $ |S| = k $, for each $ k \\in \\{1, 2, \\dots, m\\} $  \n\n**Objective**  \nFor each $ k \\in \\{1, 2, \\dots, m\\} $, compute the minimum total cost:  \n$$\n\\min \\sum_{i=1}^n x_i\n$$  \nsubject to the constraints above and $ |S| = k $.  \n\n**Note**: The set $ S $ must consist of positions that can simultaneously be local maxima under the adjusted heights. In particular, no two adjacent hills can both be in $ S $, since a hill cannot be strictly greater than both neighbors if a neighbor is also a peak. Thus, $ S $ must be an independent set in the path graph of $ n $ vertices.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF1012C","tags":["dp"],"sample_group":[["5\n1 1 1 1 1","1 2 2"],["3\n1 2 3","0 2"],["5\n1 2 3 2 2","0 1 3"]],"created_at":"2026-03-03 11:00:39"}}