Gem And Princes (UVa Live Archive Asia Beigin 2011)
問題
さめがめの最大得点を求めよ。
幅、高さ<=8
色の数<=6
解法
全探索＋枝刈りで解く。枝刈りは残ってる色の個数をそれぞれ二乗して足した数が現在の答えを上回るかどうかですれば良い。
これでなぜかACもらえけるけど、下の入力で全然終わらんのですが…。
8 8 6 1 1 2 3 4 4 5 5 1 2 2 3 3 4 5 5 3 3 4 1 1 2 6 6 3 4 4 1 2 2 6 6 1 1 2 3 4 4 5 5 1 2 2 3 3 4 5 5 3 3 4 1 1 2 6 6 3 4 4 1 2 2 6 6
追記：メモ化探索にしたら大分早くなったけど、まだ20秒くらいかかってる…。
