C-Explode'EmAll(形圧dp)


C-Explode'EmAll(形圧dp)
http://codeforces.com/gym/101246/problem/C
題意:n*mの図を与え、「*」はこの場所を爆破する必要があることを示し、爆弾が(i,j)の位置に置けば、i行j列目のすべての「*」を爆破することができる.少なくともどれだけの爆弾を捨てる必要があるかを聞いて、すべての「*」を爆破することができます.
考え方:見るからに最小頂点オーバーライドだと思っています.そして出来ないことに気づく...
枚が行われた状態i、1はこの行が爆発しないことを示し、0はこの行が爆発したことを示す.
そしてプッシュします.
ここではbitsetで行の状態を維持します.
f[i][j]は、i行目j列に「*」があるか否かを示す.
dp[i]は、爆発しない行の状態にどの列が爆発する必要があるかを示す.
num[i]は、揚げない行の数を表します.
そして各状態が最適化される.
#include 
using namespace std;
#define N 25
char s[26];
bitset f[N], dp[1<