UOJ Logo

NOI.AC

1S 128MB
Statistics

宝石排列

时间限制:1秒,内存限制:128MB

读入文件名:jewel.in

输出文件名:jewel.out

【题目描述】

巫师手中有$n$个宝石,编号从1到$n$,他要将这些宝石排成一列,相邻的宝石之间有共同作用,产生魔力。

已知任意两个宝石相邻会产生的魔力值,即若第$i$个宝石和第$j$个宝石相邻,则会产生$a_{i,j}$的魔力。宝石排列的魔力值为所有相邻宝石之间产生的魔力值之和。

问将$n$个宝石排成一列最多能产生多少魔力值。

【输入格式】

输入有$n+1$行,第一行为一个正整数$n$,表示宝石的个数。

接下来是$n$行$n$列的整数矩阵,其中第$i$行第$j$列表示$a_{i,j}$,行内数据间用一个空格分隔。

保证$a_{i,j}=a_{j,i}$,且$a_{i,i}=0$。

【输出格式】

输出一行,包含一个正整数,表示最多能产生的魔力值。

【输入输出样例1】

jewel.in

5
0 1 2 3 4
1 0 2 3 4
2 2 0 3 4
3 3 3 0 4
4 4 4 4 0

jewel.out

14

【输入输出样例2】

jewel.in

5
0 6 2 6 10 
6 0 7 10 1 
2 7 0 2 1 
6 10 2 0 9 
10 1 1 9 0

jewel.out

36

【数据规模与约定】

对于前30%的数据,$0\le a_{i,j}\le 10000$;

对于前80%的数据,$1\le n\le 10$;

对于100%的数据,$1\le n\le 16$,$0\le a_{i,j}\le 10^9$;