分类： 7.0 ~ 8.0

YZOJ P3840 [2018省队集训]序列

YZOJ P3840 [2018省队集训]序列

时间限制：2000MS      内存限制：524288KB

难度： \(8.0\)

  • 题目描述

给定一个长度为 \(n\) 的序列 \(x\) 。

你需要从序列中选出一些位置。对于第 \(i\) 个位置，如果它被选中，你会获得 \(x_i\) 的收益；否则找到最小的 \(j\) 使得第 \(j\) 个位置到第 \(i\) 个位置都没有被选中，你需要付出 \(i-j+1\) 的代价。

此外，你选出的位置必须满足 \(x_i\) 是单调不下降的。

最大化收益减去代价的结果。

  • 输入格式

第一行一个正整数 \(n\)，第二行 \(n\) 个整数 \(x_1\) ~ \(x_n\) 。

  • 输出格式

输出一行一个整数表示答案。

  • 样例 1 输入

  • 样例 1 输出

  • 样例 1 说明

选择第 \(1, 3, 5, 7\) 个位置，获得收益 \(1+2+3+4=10\) ，第 \(2, 4, 6\) 个位置的代价分别为 \(1, 1, 1\) ，收益减去代价为 \(10-3=7\) 。

  • 样例 2 输入

  • 样例 2 输出

  • 数据规模与约定

对于 \(5\%\) 的数据， \(1 \leq n \leq 5\) 。…

[CEOI2017]Building Bridges

[CEOI2017]Building Bridges

时间限制：1000MS      内存限制：131072KB

难度： \(7.2\)

  • 题目描述

有 \(n\) 根柱子依次排列，每根柱子都有一个高度。第 \(i\) 根柱子的高度为 \(h_i\) 。

现在想要建造若干座桥，如果一座桥架在第 \(i\) 根柱子和第 \(j\) 根柱子之间，那么需要 \((h_i-h_j)^2\) 的代价。
在造桥前，所有用不到的柱子都会被拆除，因为他们会干扰造桥进程。第 \(i\) 根柱子被拆除的代价为 \(w_i\)​，注意 \(w_i\) 不一定非负，因为可能政府希望拆除某些柱子。

现在政府想要知道，通过桥梁把第 \(1\) 根柱子和第 \(n\) 根柱子连接的最小代价。注意桥梁不能在端点以外的任何地方相交。

  • 输入格式

第一行一个正整数 \(n\) 。

第二行 \(n\) 个空格隔开的整数，依次表示 \(h_1, h_2, \cdots, h_n\) 。

第三行 \(n\) 个空格隔开的整数，依次表示 \(w_1, w_2, \cdots, w_n\) 。

  • 输出格式

输出一行一个整数表示最小代价，注意最小代价不一定是正数。

  • 样例输入

  • 样例输出

  • 数据范围与提示

对于 \(30\%\) 的数据，有 \(1 \leq n \leq 1000\) ；

对于另外 \(40\%\) 的数据，有 \(\left| w_i \right| \leq 20\) ，保证存在一种最优方案，除了头尾两根柱子外，最多只保留两根柱子；

对于 \(100\%\) 的数据，有 \(2 \leq n \leq 10^5\)，\(0 \leq h_i,\left| w_i\right| \leq 10^6\) 。

数据来源 LOJ 2483 。

 

 

已搬至 YZOJ P4254 。…

[SDOI2012]任务安排

[SDOI2012]任务安排

时间限制：1000MS      内存限制：131072KB

难度： \(7.1\)

  • 题目描述

按顺序给定 \(N\) 个子任务，每个任务用时 \(t_i\) ，费用系数 \(f_i\)。

可以把连续的若干个（或一个）子任务合成为一个大任务，大任务的用时和费用系数分别为其中每个子任务的用时之和与费用系数之和。开始一个大任务之前需要准备时间 \(S\)，一个大任务的费用为他的 完成时刻 \(\times\) 费用系数 ，问按顺序执行完所有的大任务后，最小的费用和为多少。

形式化的，将 \(N\) 个任务划分成若干个块，每一组任务 \(M_i\) 花费代价 \((T+\sum{t_j}+S) \times \sum{f_j}\)，\(j \in M_i\)，\(T\) 为执行到这个任务之前花费的时间，求执行完所有任务的最小代价和。

  • 输入格式

第一行一个整数 \(N\) ；

而后 \(N\) 行中，第 \(i\) 行包含一个可能为负的整数 \(t_i\) 和一个非负整数 \(f_i\) 。

  • 输出格式

一个整数，表示最小的代价和。

  • 样例输入

  • 样例输出

  • 样例说明

如果分组方案是 \(\{1,2\}\)、\(\{3\}\)、\(\{4,5\}\)，则完成时间分别为 \(\{5,5,10,14,14\}\)，费用 \(C=\{15,10,30,42,56\}\)，总费用就是 \(153\) 。

  • 数据规模与约定

对于 \(20\%\) 的数据，\(1 \leq N \leq 1000\) ；

对于另外 \(40\%\) 的数据， \(1 \leq N \leq 300000\) ；

对于前 \(60\%\) 的数据，\(0 \leq t_i \leq 2^8\) ；

对于后 \(40\%\) 的数据，\(1 \leq N \leq 100000\)，\(-2^8 \leq t_i \leq 2^8\) ；

对于 \(100\%\) 的数据， \(0 \leq S, f_i …

YZOJ P3129 [校内训练20170627]跳格子

YZOJ P3129 [校内训练20170627]跳格子

时间限制：1000MS 内存限制：524288KB

难度：\(7.0\)

  • 题目描述

在一个花园里有一排 \(n\) 个格子，这些格子编号为 \(1\) 到 \(n\) 。袋鼠喜欢在花园的格子上跳跃。

袋鼠的跳跃方式是这样的：一开始，袋鼠位于 \(s\) 号格子上，接着它会选择一个尚未经过的格子上跳跃，经过 \(n-1\) 次跳跃后，所有格子都被经过了一次，袋鼠的跳跃将结束。袋鼠总是会在 \(t\) 号格子结束跳跃。

由于袋鼠中了病毒，所以如果上一步往前跳，那么这一步必须往后跳；反之，若上一步往后跳，那么这一步往前跳。

请问袋鼠有多少种跳跃的方案呢？

形式化地，你需要求出有多少个 \(1\) 到 \(n\) 的排列 \(p_1, p_2, \cdots, p_n\)，满足：

1， \(p_1=s ，p_n=t\)；

2， 对任意 \(2 \leq i \leq n-1\)，或者 \((p_i-1<p_i) \land (p_i+1<p_i)\) ，或者 \((p_i-1>p_i) \land (p_i+1>p_i)\) 。

  • 输入格式

输入共一行，包含三个正整数 \(n, s, t\) 。

  • 输出格式

输出共一行，包含一个整数，表示跳跃的方案数对 \(1,000,000,007\) 取模的结果。

  • 样例输入【包含两组样例】

  • 样例输出

  • 样例 1 说明

从 \(2\) 号格子到 \(3\) 号格子的跳跃方案有两种，一种是 \(2,1,4,3\)，一种是 \(2,4,1,3\) 。

  • 数据规模与约定

 

 

 …