TURNOFFTHELIGHTS.. 감을 못잡겠네요ㅠㅠ

  • User Avatar
    restart

    [[problem:TURNOFFTHELIGHTS]]를 풀고 있는데요, 사흘간 자나깨나 기회될때마다 관계식을 떠올리려 노력해도 도저히 나오질 않네요.. 다른 문제도 손에 잡히질 않고 입맛도 떨어지고 고민만 늘어가는 중.. 도저히 안되겠다 싶어서 도움의 손길을 청합니다.ㅠㅠ

    지금까지 제가 생각했던 건
    dp(i,j)=i를 행번호, j를 각행이 열변환되었는지 비트별로 나타낸다고 할 때($0110_2$ : 1열, 2열이 열변환되었음), i행을 j열변환시키면서 [0..i]행을 모두 0으로 만드는 최소 가짓수라 정의하고

    $dp[i][j]=min(dp[i-1][k]+bitcnt(j-k \And j)+linear[row_i \oplus j]), k=0..2C$
    $\And$ = 비트AND, $ \oplus $ = 비트XOR

    인데요... 1차원의 행변환의 해를 구하는 linear는 미리 계산해 둬서 O(1)이라 해도 시간복잡도가 $O(R2{2C})$라 답이 없더라구요...ㅠㅠ

    부족한 제게 가르침을 부탁합니다.. dp는 너무 형태가 다양하네요..ㅠㅠ


    11년 전
8개의 댓글이 있습니다.
  • User Avatar
    일루

    거의 다 오신것 같습니다. 가능한 (j, k)의 pair에 대해 생각해보시면...


    11년 전 link
  • User Avatar
    WeissBlume

    현재 점화식 정의에서 상태를 나타내는 변수를 늘리면 더 쉽게 해결 가능합니다.

    d[i][j][k][l] : i를 행번호, j를 열번호, k를 각 열이 뒤집어진 상태인가, l을 현재 행을 뒤집는 중인가(연속적으로 뒤집을 수 있으니까).
    이렇게 정의하면 현재 (행,열)위치에서만 뒤집어보면 되니까 시간 안에 충분히 수행되겠죠!


    11년 전 link
  • User Avatar
    wookayin

    2011년 대회 당시 공개했던 솔루션 슬라이드 입니다. 좀 더 오래 고민해보시고 도저히 모르시겠으면 참고하세요~


    11년 전 link
  • User Avatar
    restart

    일루/ j에서 고려하는 k를 제한해보려고 했는데, 그게 잘 안됩니다..ㅠㅠ
    11
    11
    11
    00
    의 경우를 생각해보면, dp[3][00]에 답이 있을 텐데, 이건 dp[2][11]→dp[1][11]→dp[0][11]로 연결이 되는데.. 결국 고려하는 k의 범위가 00~11에 놓여 있다는 거고, j에 의존하지 않는 것 같아서요..ㅠㅠㅠ


    11년 전 link
  • User Avatar
    restart

    WeissBlume/

    저도 열번호를 상태공간에 포함시키려 계속 노력했는데, [i][j-1]과 [i][j]간 연관관계가 뚜렷하지 않아 번번히 막히고 있습니다.ㅠㅠ 정의상 i*(j-1)과 i*j의 부분해일텐데,
    ＠＠＠Ａ
    ＠＠＠Ａ
    ＠＠＠Ａ
    ＃＃＃＊
    ＊이 현재 고려하는 dp[i][j][k][l]이라 할 때, dp[i][j-1][..][..]를 이용해 해당 부분해를 구해야 할텐데, 항상 Ａ에서 추가발생하는 부분이 문제가 됩니다. 이걸 또 따로 가지고 있어야 하는걸까요..ㅠㅠ으으으


    11년 전 link
  • User Avatar
    restart

    wookayin/ 슬라이드가 공개되지 않은 것 같습니다.ㅜㅜ not found가 뜨네요..


    11년 전 link
  • User Avatar
    restart

    뭔가 답까지 한계단 남은 것 같은데 눈앞에 길을두고 헤메는 느낌이라 엄청 답답하네요-_-;; 으아!


    11년 전 link
  • User Avatar
    restart

    해결했습니다:) 5일간 끙끙 앓았네요..ㅠㅠ


    11년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.