[일반] 개씹뉴비 비트dp

[익명(222.112)]

공부자료좀 늅늅

[익명(222.112)]

라기보단 본질적으로 비트마스킹이 약한듯?

[익명(222.112)]

사이즈가 2면 0101 0110 0011 1001 1100 ... 이런 식으로 순회돌아야 하는데 어케할지 모르겠네

[익명(222.112)]

해커의 기쁨에 뭔가 나올거같기도 하고 뒤져봐야지

[익명(222.112)]

없다

[해당 댓글은 삭제되었습니다.]

해당 댓글은 삭제되었습니다.

[익명(222.112)]

int n = 4, k = 2; const ll lim = 1LL << n; for (ll x = (1LL << k) - 1; x < lim; x = (x+(x&-x)) | ((x ^ (x+(x&-x))) / (x & -x)) >>2) cout << bitset<4>(x) << '\n';

[익명(222.112)]

쪼까 더럽누...
https://codeforces.com/blog/entry/82379

[익명(222.112)]

더러운걸 떠나서 이해를 포기한다.

[익명(222.112)]

저기엔 이게 없어. tsp를 bottom up으로 풀려면 (방식에 따라 차이가 있긴 하겠지만) 저게 필요하더라...

[익명(222.112)]

v1에서 출발하고 나머지 모든 정점을 방문하고 v1으로 돌아오는 최단거리를 D[v1][V-{v1}]으로 해놓으면, D[v2][∅], D[v3][∅], D[v4][∅]부터 D[v2][{v3}], D[v2][{v4}], D[v3][{v2}], D[v3][{v4}], D[v4][{v2}], D[v4][{v3}] 채우고

[익명(222.112)]

D[v2][{v3,v4}], D[v3][{v2,v4}], D[v4][{v2,v3}] 채운 다음에 D[v1][{v2,v3,v4}]를 채워서 답 구하는 것

[익명(222.112)]

차례대로 사이즈 1부터 사이즈 4까지 각각 k개로 구성된 비트 마스크 조합을 구해야 함.

[익명(222.112)]

내 풀이는 뭔가 더럽네.. 책보고 그대로 따라한건데

[익명(222.112)]

고맙다 아무튼. 뭔가 내 방식이랑 역순인거같네