ビットDP 練習問題 2 Python2編（paizaランク A 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
paiza 高校には N 人の生徒がいます（N は偶数）。
paiza 高校では、各生徒に番号が振られており、人 i (1 ≦ i ≦ N) と番号で呼ばれています。
いまから N 人の生徒全員を 2 人ペアにします。
どの人も誰か 1 人とペアにならなければなりません。
人 i と人 j (i ≠ j) がペアになるとき、そのペアの相性を A_{i,j} とします。
できたペアの相性の総和の最大値を求めてください。
入力例 1 では、人 1 と人 2、人 3 と人 4 がペアになるとき、相性の総和は 9 となります。
相性の総和が 10 以上になるようにペアを作ることはできないので、9 を出力します。
- 入力される値
-
入力は以下のフォーマットで与えられます。
N
A_{1,1} A_{1,2} ... A_{1,N}
A_{2,1} A_{2,2} ... A_{2,N}
...
A_{N,1} A_{N,2} ... A_{N,N}
・ 1 行目には、生徒数を表す整数 N が与えられます。
・ 続く N 行には、ペアの相性を表す整数 A_{i,j} が与えられます。
・ 入力は合計で 1 + N 行からなり、入力値最終行の末尾に改行が 1 つ入ります。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
できたペアの相性の総和の最大値を求めてください。
末尾に改行を入れ、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 2 ≦ N ≦ 18
・ N は偶数
・ 0 ≦ A_{i,j} ≦ 10^9
・ A_{i,i} = -1
・ A_{i,j} = A_{j,i}
- 入力例1
-
4
-1 2 3 4
2 -1 4 3
3 4 -1 7
4 3 7 -1
- 出力例1
-
9
- 入力例2
-
8
-1 695412038 751766543 870982138 810077061 628767715 912198709 689865810
695412038 -1 688114257 793818771 618751826 821848878 998285316 976226834
751766543 688114257 -1 563628562 623866690 553477694 550644745 512176812
870982138 793818771 563628562 -1 933128146 530984426 712606276 960162630
810077061 618751826 623866690 933128146 -1 791417082 795433834 616368776
628767715 821848878 553477694 530984426 791417082 -1 840583295 608460785
912198709 998285316 550644745 712606276 795433834 840583295 -1 969331691
689865810 976226834 512176812 960162630 616368776 608460785 969331691 -1
- 出力例2
-
3501704818
