本题中，你需要解决一个著名的 NP 问题——二次整数规划问题。

\n

二次整数规划问题要有变量：你需要给出一个长度为 $n$ 的整数序列 $(x_1, x_2, \\cdots, x_n)$，满足下文中的所有条件。

\n

二次整数规划问题要有约束：你给出的整数序列需要满足以下两类约束：

\n

一类约束是单个变量取值的约束：给出正整数 $k$（$3 \\le k \\le 5$）和 $n$ 个区间 $[l_i, r_i]$（$1 \\le i \\le n$），其中 $1 \\le l_i \\le r_i \\le k$，你给出的序列需要满足 $\\forall 1 \\le i \\le n$，$l_i \\le x_i \\le r_i$；
另一类约束是变量之间取值的约束：给出 $m$ 个三元组 $(p_i, q_i, b_i)$，你给出的序列需要满足 $\\forall 1 \\le j \\le m$，$| x_{p_j} - x_{q_j} | \\le b_j$。

\n

二次整数规划问题要有目标函数：在给出 $k-2$ 个目标参数 $v_2,v_3,\\cdots,v_{k-1}$（注意下标范围为 $2$ 至 $k-1$）的前提下，对于一个值域为 $[1, k]$ 的整数数列 $\\{p_1, p_2, \\cdots, p_n\\}$，设 $c_i$ 为该序列中取值为 $i$ 的元素个数，$G$ 为满足 $1 \\le i, j \\le n$ 且 $|p_i-p_j|\\leq 1$ 的整数二元组 $(i, j)$ 个数，注意当 $i \\neq j$ 时，$(i, j)$ 与 $(j, i)$ 是不同的二元组。定义该序列的权值为

\n

$$ W(p_1, p_2, \\cdots, p_n) = 10^6 G+\\sum_{i=2}^{k-1} c_i v_i . $$

\n

你的序列需要在满足以上两类约束的情况下，最大化其权值。

\n

二次整数规划问题不一定要有多组询问，但是我们会给出 $q$ 次询问，每次询问给出不同的权值参数 $v_2, v_3, \\cdots, v_{k-1}$，对于每组询问你需要找到满足约束的最大化权值的序列。为了减少输出量，你只需要输出这个序列的权值。

\n

输入格式

\n

本题有多组测试数据。 第一行一个非负整数和一个正整数 $C, T$，分别表示测试点编号和测试数据数量。$C = 0$ 表示该组数据为样例。

\n

对于每组测试数据，第一行四个整数 $k, n, m, q$，描述序列值域、序列长度、变量之间约束的个数和询问次数。

\n

接下来 $n$ 行每行两个整数 $l_i, r_i$，描述序列中每个元素对应的取值区间。

\n

接下来 $m$ 行每行三个整数 $p_j, q_j, b_j$，描述一个变量之间的约束。

\n

接下来 $q$ 行每行 $k-2$ 个非负整数 $v_2, v_3, \\cdots, v_{k - 1}$ 描述一组询问的权值参数。

\n

数据保证在给定的约束条件下，至少存在一组满足所有约束的序列。

\n

输出格式

\n

对于每组数据的每组询问输出一行一个整数，表示序列权值的最大值。

\n

样例一

\n

见附件下载。

\n

该样例满足数据范围中测试点 $1$ 的性质。

\n\n

第一个测试数据中两组询问对应的最优序列均为 $(1, 2, 2, 1, 3)$，有 $c_2=2, G=21$。

\n

样例二

\n

见附件下载。

\n

该样例满足数据范围中测试点 $3$ 的性质。

\n\n

第一个测试数据中两组询问对应的一个最优序列分别为 $(4, 4, 3, 3)$ 和 $(4, 3, 2, 2)$。

\n

样例三

\n

见附件下载。

\n

该样例满足数据范围中测试点 $5$ 的性质。

\n\n

第一个测试数据中三组询问对应的一个最优序列分别为 $(3, 3, 3, 3, 3)$、$(2, 2, 3, 3, 2)$ 和 $(3, 2, 4, 4, 2)$。

\n

样例四

\n

见附件下载。

\n

该样例满足数据范围中测试点 $2$ 的性质。

\n

样例五

\n

见附件下载。

\n

该样例满足数据范围中测试点 $4$ 的性质。

\n

样例六

\n

见附件下载。

\n

该样例满足数据范围中测试点 $8$ 的性质。

\n

样例七

\n

见附件下载。

\n

该样例满足数据范围中测试点 $14$ 的性质。

\n

样例八

\n

见附件下载。

\n

该样例满足数据范围中测试点 $17$ 的性质。

\n

子任务

\n

设 $\\sum q$ 为单个测试点中所有测试数据的 $q$ 的和。对于所有测试点，

\n

$1 \\le T \\le 600$，
第 $i$ ($1 \\le i \\le T$) 个测试数据中，$1 \\le n \\le \\max\\left(\\frac{T}{i},2 \\log_2{T}\\right)$，
$3 \\le k \\le 5$，$0 \\le m \\le 3n$，$1 \\le q,\\sum q \\le 3 \\times 10^5$，
$1 \\le l_i \\le r_i \\le k$，
$1 \\le p_j,q_j \\le n$，$0 \\le b_j < k$，
$0 \\le v_2,\\cdots,v_{k-1} \\le {10}^{12}$。

\n

统计

递交统计

【NOI2022】二次整数规划问题

信息

还没有账户？

登录