STARFORCE 문제 다시 질문드립니다..

  • juhosung
    juhosung

    이전에 STARFORCE 문제 질문을 드리고 나서..
    코드를 새롭게 다시 짯습니다.
    다시 제출했는데, 여전히 오답이 뜨는데요..
    코드 어느 부분에서 제가 간과하는게 있는지.. 확인 좀 부탁드립니다.
    대략적인 알고리즘은 아래와 같구요. 코드를 통해서 보는게 훨씬 이해가 빠를 것 같습니다.

    • 이전 강화의 특정 카드위치(j) 에서의 최적값을 통해서, 현재 강화의 최적값을 구함.
    #include <cstdio>
    #include <bitset>
    #include <cstring>
    
    using namespace std;
    
    int N,M,nCase,OR[210][210],t[210][210];
    
    
    int main()
    {
        scanf("%d",&nCase);
        while (nCase--) {
    
            scanf("%d%d",&N,&M);
            memset(OR, 0, sizeof(OR));
            memset(t, 0, sizeof(t));
    
            for(int i=1; i<=N; ++i)
            {
                scanf("%d",&OR[i][i]);
                for(int j=i-1; j>=1; --j)
                    OR[j][i] = OR[j+1][i] | OR[j][j];
            }
    
            t[0][0] = 65535;
    
            for(int i=1; i<=M; ++i)
            {
                int l = N-M+i-1;
    
                if(i==1) l = 0;
    
                //prev
                for(int j=i-1; j <= l; ++j)
                {
                    int nl = N-M+i;
                    //cur
                    for(int k=j+1; k<=nl; ++k)
                    {
                        int val = t[i-1][j] & OR[j+1][k];
    
                        if(bitset<16>(val).count() > bitset<16>(t[i][k]).count())
                            t[i][k] = val;
                    }
                }
            }
            printf("%d\n",bitset<16>(t[M][N]).count());
        }
        return 0;
    }
    

    감사합니다.


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