글 읽기 - 비트마스크 다이나믹으로 하려고하는데....

crasy111 7년 전 0

2차원 비트마스크로 하려고합니다.

[2^(N-1)][N] 만큼 잡고요...

D[i][j]가 arr[j][k]값보다 작거나 같으면 j번째 사람이 k번째 사람에게 팔 수 있으므로 팔고, D[i|(1<<k)][k]값은 arr[j][k]로 두었습니다.

점화식이 잘못 되었나요...?

#include<stdio.h>
#include<memory.h>

int check[32770],dy[32770][16],arr[16][16],n;

int main()
{
    scanf("%d",&n);
    int i,j,k,ans=1,cnt;
    for(i=0;i<n;i++) for(j=0;j<n;j++) scanf("%1d",&arr[i][j]);

    memset(dy,99,sizeof(dy));
    dy[1][0]=0; check[1]=1;
    for(i=1;i<(1<<n);i++){
        if(!check[i]) continue;
        for(cnt=j=0;j<n;j++)if((1<<j)&i) cnt++;
        if(cnt>ans) ans=cnt;
        for(j=0;j<n;j++)if(((1<<j)&i)){
            for(k=0;k<n;k++)if(!((1<<k)&i) && dy[i][j]<=arr[j][k]){
                dy[i|(1<<k)][k]=arr[j][k];
                check[i|(1<<k)]=1;
            }
        }
    }
    printf("%d",ans);
    return 0;
}

yukariko 7년 전 0

사람의 최대값을 구하려면 그림을 팔때마다 최대한 가격의 증가폭을 줄여야 하겠죠?

그런데 지금 코드에는 그런 처리가 없습니다. 단순히 살 수 있으면 그 가격을 저장하는 방법만이 사용되고 있죠.

즉, dy[i|(1<<k)][k] 에는 i | (1 << k) 만큼을 거치면서, 그림이 k 에 있는 경우들 중 가장 가격변동이 작은것이 저장되어있어야 합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

비트마스크 다이나믹으로 하려고하는데....

crasy111 7년 전 0

yukariko 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말