글 읽기 - 11577번 힌트 좀 부탁드립니다 ㅜㅜ

phs1116 7년 전 0

아무리 해도 자꾸 TLE가 뜨네요.

입력이 최대 10만개라 DP로 해야되는건지... 어떻게 접근할지도 모르겠고...

힌트나 조언 좀 부탁드립니다...

#include <cstdio>
#include <cstring> 
#include <algorithm>
#define BLOCK 32
#define MAX_VAL 987654321
unsigned int bitmask[3130];
int N,K;

void toggle_range(unsigned int *bitmask,int begin,int amount){
   int end=begin+amount-1;
   if(begin/BLOCK==end/BLOCK){
       bitmask[begin/BLOCK]^=(~0<<(begin%BLOCK))&~(~0<<(end%BLOCK)<<1);
       return;
   }
   bitmask[begin/BLOCK]^=(~0<<(begin%BLOCK));
   for(int i=begin/BLOCK+1;i<end/BLOCK;i++)
       bitmask[i]^=~0;
   bitmask[end/BLOCK]^=~(~0<<(end%BLOCK)<<1);
}
 
int popcnt(unsigned int *bitmask) {
   int sum = 0;
   for (int i = 0; i <=N/32; i++)
       sum += __builtin_popcount(bitmask[i]); 
   return sum;
}
int CDS(int n, int count){
	int on = popcnt(bitmask);
	if(on == 0) return count;
	if(n == N-K+1) return MAX_VAL; 
	int ret = CDS(n+1,count);	
	toggle_range(bitmask,n,K);
	ret = std::min(ret,CDS(n+1,count+1));
	return ret;	 
}
 
int main(){
	memset(bitmask,0,sizeof(bitmask));
	scanf("%d %d",&N,&K);
	for(int i = 0; i<N; i++){
		int input;
		scanf("%d",&input);
		if(input==1) bitmask[i/BLOCK]|=(1<<i%BLOCK);
	}
	int ret = CDS(0,0);
	printf(ret==MAX_VAL?"Insomnia":"%d",ret);
}

chogahui05 7년 전 0

1080번은 푸셨나요? 사실, 1080번의 풀이를 아시더라도 쉽지는 않아요.

그 이유는 N이 10만이나 되기 때문이지요.

K도 최대 10만까지 가고요.

Queue를 쓰면 해결되는 문제입니다.

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

문제

문제

출처

ICPC

11577번 힌트 좀 부탁드립니다 ㅜㅜ

phs1116 7년 전 0

chogahui05 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말