[Medium] FiveHundredEleven
Topcoder SRM 511 Div1
D[turns][memory] = 둘이 합쳐 turns장의 카드를 사용했고 현재 메모리상태가 memory 일 때
이 상황을 받은 사람이 이길 수 있는가?
memory | c = memory 인 카드 c의 개수를 k장이라 해보자.
그 k장 중 (k - turns)장 만큼은 memory 에 OR를 해도 메모리 값이 변하지 않는다.
그 k장 중 turns장 은 이미 쓰인 카드다.
k장을 제외한 나머지 카드는 memory 에 OR를 하면 무조건 값이 변한다.
여기서 (k - turns)장이 실제로 어떤 카드인지는 중요하지 않다. OR를 해도 어차피 메모리가 변하지 않으니까.
k - turns > 0 이면 D[turns + 1][memory] 를 참조
나머지 값이 변하는 카드에 대해 D[turns + 1][memory | c] 를 참조
하여 dp값을 구하자