http://arc078.contest.atcoder.jp/tasks/arc078_d
3^Nの形になるdpなんて初めて見た。
まず使う辺に注目して、それらのコストの和を最大化する。
dp[S][v]:=(集合Sの点を使う際で0~v間でpathがただ一つ存在するための最大値)とする。
遷移は二種類ある。
(1)path上の点を追加する。
(2)vにpathが増えないよう点をくっつける。
(1)は問題ないが、(2)は4^Nかかるように見える。
しかし実際は3^Nとなり、適当に定数倍改善すれば十分高速。
なぜ3^Nになるかというと、いま注目すべきものは、
「S⊃T⊃Uとなる(T,U)が何個あるか」という問題と同値である。
各bitについて「Tに選ばれない」「Tにのみ選ばれる」「T,Uともに選ばれる」の三種類があるので、結局(T,U)のペアは3^Nとなる。
int N, M; int dp[(1 << 16)][16]; int cost[(1 << 16)]; int A[500], B[500], C[500]; int E[50]; int D[50][50]; void solve() { cin >> N >> M; memset(D, -1, sizeof(D)); int res = 0; rep(i, 0, M) { cin >> A[i] >> B[i] >> C[i]; A[i]--; B[i]--; D[A[i]][B[i]] = C[i]; D[B[i]][A[i]] = C[i]; res += C[i]; } rep(bit, 0, (1 << N)) { rep(j, 0, M) { if((bit & (1 << A[j])) && (bit & (1 << B[j]))) { cost[bit] += C[j]; } } } rep(bit, 0, (1 << N)) rep(j, 0, N) dp[bit][j] = -inf; dp[1][0] = 0; rep(bit, 0, (1 << N)) { rep(i, 0, N) { if(!(bit & (1 << i)) || dp[bit][i] < 0) continue; rep(j, 0, N) { if(!(bit & (1 << j)) && D[i][j] != -1) { MAX(dp[bit | (1 << j)][j], dp[bit][i] + D[i][j]); } } int n = 0; rep(j, 0, N) { if(!(bit & (1 << j))) { E[n++] = j; } } rep(mask, 0, (1 << n)) { int nbit = 0; rep(k, 0, n) { if(mask & (1 << k)) { nbit |= (1 << E[k]); } } MAX(dp[nbit | bit][i], dp[bit][i] + cost[nbit | (1 << i)]); } } } int tmp = dp[(1 << N) - 1][N - 1]; cout << res - tmp << "\n"; }