当前你的浏览器版本过低，网站已在兼容模式下运行，兼容模式仅提供最小功能支持，网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器：

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

5691：Sitting in Line

题目描述
度度熊是他同时代中最伟大的数学家，一切数字都要听命于他。现在，又到了度度熊和他的数字仆人们玩排排坐游戏的时候了。游戏的规则十分简单，参与游戏的N个整数将会做成一排，他们将通过不断交换自己的位置，最终达到所有相邻两数乘积的和最大的目的，参与游戏的数字有整数也有负数。度度熊为了在他的数字仆人面前展现他的权威，他规定某些数字只能在坐固定的位置上，没有被度度熊限制的数字则可以自由地交换位置。
输入解释
第一行一个整数$T$，表示$T$组数据。
每组测试数据将以如下格式从标准输入读入：

$N$

$a_1 p_1$

$a_2 p_2$

:

$a_N P_N$

第一行，整数 $N (1 \leq N \leq 16)$，代表参与游戏的整数的个数。

从第二行到第 $(N + 1)$ 行，每行两个整数，$a_{i} (-10000 \leq a_{i} \leq 10000)$、$p_{i} (p_{i} = -1$ 或 $0 \leq p_{i} < N)$，以空格分割。$a_{i}$代表参与游戏的数字的值，$p_{i}$代表度度熊为该数字指定的位置，如果$p_{i} = -1$，代表该数字的位置不被限制。度度熊保证不会为两个数字指定相同的位置。
输出解释
第一行输出："Case #i:"。$i$代表第$i$组测试数据。

第二行输出数字重新排列后最大的所有相邻两数乘积的和，即$max\{a_1\cdot a_2+a_2\cdot a_3+......+a_{N-1}\cdot a_N\}$。
输入样例 
2
6
-1 0
2 1
-3 2
4 3
-5 4
6 5
5
40 -1
50 -1
30 -1
20 -1
10 -1
输出样例 
Case #1:
-70
Case #2:
4600
来自杭电HDUOJ的附加信息
Recommend wange2014
该题目是Virtual Judge题目，来自 杭电HDUOJ
题目来源 2016"百度之星" - 初赛（Astar Round2A）
源链接： HDU-5691
最后修改于 2020-10-25T23:24:50+00:00 由爬虫自动更新
共提交 0 次
通过率 --%
时间上限 内存上限
10000/5000MS(Java/Others) 262144/262144K(Java/Others)