ABC056 C - 部門分け
解法
まずは、制約からbitDPをエスパーで思いつきます。
グループの状態がのとき、これを分割したときに作成できるスコアの最大値
とします。はビットにより表現できます。
を分割して、とに分けたときに、とから任意に1人ずつ選んだ時の信頼度の総和をとすると、この値だけスコアが下がることになります。
すると、
と表現することができます。
また、グループが1人の状態の場合は自動的に最大値は0になります。
答えは、全員が1つのグループになっている状態を表す状態をとしたとき、となります。
あとは、を高速に求めることができれば、満点を取ることができます。
グループの状態がの場合、の中での任意の2人に対する信頼度の総和
とすると、これはで求めることができます。
このとき、をとに分割した場合のは、
の計算をすることで、なんとで求めることができます。
あとは、上のDPを行うことで答えを求めることができます。