結果

問題 No.90 品物の並び替え
ユーザー fmhrfmhr
提出日時 2017-01-28 15:52:08
言語 Go
(1.22.1)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 774 bytes
コンパイル時間 17,037 ms
コンパイル使用メモリ 240,680 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-06 07:46:54
合計ジャッジ時間 14,574 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 1 ms
5,248 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 1 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import "fmt"

func main() {
	var N uint
	var M int
	fmt.Scan(&N, &M)
	var t [100][100]uint
	var a, b int
	var c uint
	for i := 0; i < M; i++ {
		fmt.Scan(&a, &b, &c)
		t[a][b] = c
	}
	var d [512]uint
	for i := 0; i < 1<<N; i++ {
		for j := uint(0); j < N; j++ {
			// すでに使ってる
			if i&(1<<j) != 0 {
				continue
			}
			// nはビットで使用したアイテムを表してる
			n := i | 1<<j
			s := d[i]
			for k := uint(0); k < N; k++ {
				if i&(1<<k) == 0 {
					continue
				}
				// まだ使ってないアイテムk,jの値を足す
				s += t[k][j]
			}
			d[n] = max(s, d[n])
		}
	}
	fmt.Println(d[1<<N-1])
}

func max(a, b uint) uint {
	if a > b {
		return a
	}
	return b
}

// 参照http://yukicoder.me/submissions/76498
// bitDP?
0