编程介的小学生 2020-02-02 21:57 采纳率: 20.5%
浏览 147

A Captivating Match

Problem Description
The FIFA 2010 Soccer World Cup has gone, Small Jan returned to her own planet. After she saw the Spain emerged the biggest winner, she believe that, as a Queen, she can also arrange a captivating match-International Cavalry PK Contest(ACM-ICPC) for her lovely and hard working subjects. But her subjects are so busying that they have no time to watch the group match. So, our smart Queen wants to make the final more valuable. Every Knight has a value in people’s minds and the final’s value is dependent on the last valiancy Knights (equals to the winner's value).
Now assuming that the Knights have been numbered from 1 to N, and any time Small Jan could arrange a match between any two Knights adjacent to each other, but the loser will quit. For example, (1, 2, 3, 4, 5),if the Queen arranged Knights 3 and 4 for a match and Knight 3 lost, then Knights 2 and 4 would be adjacent to each other (the result of each Knight competing with others is saved in a table).
Here, Small Jan want to know the max value of the final, can you help her?

Input
The first line of the input is a single positive integer T(0 < T <= 30), telling the number of test scenarios to follow.
Each scenario begins with a line containing an integer N, 0 < N <= 100, being the number of Knights.
The following line contains N integers, 0 < Vi < 1000, being the value of each Knight in people’s minds.
Thelast is a N × N matrix. If a[i,j] = 1 indicate when Knight i competing with j, Knight i always win, which also means a[j, i] must equals 0 and if i=j, a[i,j] must equals 0.

Output
For each input case, output a line containing a single number, which is the max value of the final, following the case number (start with 1)

Sample Input
2
3
1 2 3
0 1 0
0 0 1
1 0 0
3
1 2 3
0 1 1
0 0 0
0 1 0

Sample Output
Case 1: 3
Case 2: 1

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥20 iqoo11 如何下载安装工程模式
    • ¥15 本题的答案是不是有问题
    • ¥15 关于#r语言#的问题:(svydesign)为什么在一个大的数据集中抽取了一个小数据集
    • ¥15 C++使用Gunplot
    • ¥15 这个电路是如何实现路灯控制器的,原理是什么,怎么求解灯亮起后熄灭的时间如图?
    • ¥15 matlab数字图像处理频率域滤波
    • ¥15 在abaqus做了二维正交切削模型,给刀具添加了超声振动条件后输出切削力为什么比普通切削增大这么多
    • ¥15 ELGamal和paillier计算效率谁快?
    • ¥15 蓝桥杯单片机第十三届第一场,整点继电器吸合,5s后断开出现了问题
    • ¥15 file converter 转换格式失败 报错 Error marking filters as finished,如何解决?