ACMORE
Vjudge
杭电HDUOJ
杭电HDUOJ
北京大学POJ
Sitting in Line
登陆
注册
题目
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-25 23:24:50 UTC
由爬虫自动更新
共提交
0
次
通过率
--
%
时间上限
内存上限
10000/5000MS(Java/Others)
262144/262144K(Java/Others)
·
·
·
·
登陆或注册
以提交代码