글 읽기 - <다이어트> 반례 부탁드립니다

0203peter 2년 전 0

도저히 문제를 못찾겠어요 ㅠㅠ 부탁드립니다

#include<bits/stdc++.h>
using namespace std;
int n;
int ff=0;
int cont=1000000;
int ma[20];
int mb[20];
int mc[20];
int md[20];
int mn[20];
int ctc[20];
int ctnr[20];
int rmb[20];
int rma[20];

void boof(int q,int p){
	
	if(ctnr[1]>=ctc[1]&&ctnr[2]>=ctc[2]&&ctnr[3]>=ctc[3]&&ctnr[4]>=ctc[4]){
		ff=1;
		if(cont>p){
			cont=p;
			for(int i=0;i<q;i++) rma[i]=rmb[i];
			return;
		}
		return;
	}	
	
	if(q==n){
		if(ctnr[1]<ctc[1]||ctnr[2]<ctc[2]||ctnr[3]<ctc[3]||ctnr[4]<ctc[4]){
			return;
		}
		ff=1;
		if(cont>p){
			cont=p;
			for(int i=0;i<n;i++) rma[i]=rmb[i];
		}
		return;
	}
	
	ctnr[1]+=ma[q];
	ctnr[2]+=mb[q];
	ctnr[3]+=mc[q];
	ctnr[4]+=md[q];
	rmb[q]=1;
	boof(q+1, p+mn[q]);
	ctnr[1]-=ma[q];
	ctnr[2]-=mb[q];
	ctnr[3]-=mc[q];
	ctnr[4]-=md[q];
	
	rmb[q]=0;
	boof(q+1, p);
		
}
int main(){
	cin>>n;
	cin>>ctc[1]>>ctc[2]>>ctc[3]>>ctc[4];
	for(int i=0;i<n;i++) cin>>ma[i]>>mb[i]>>mc[i]>>md[i]>>mn[i];
	
	boof(0,0);
	
	if(ff==0){
		cout<<"-1";
		return 0;
	}
	
	cout<<cont<<'\n';
	for(int i=0;i<n;i++){
		if(rma[i]==1){
			cout<<i+1<<' ';
		}
	}
}

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

문제

문제

출처

ICPC

<다이어트> 반례 부탁드립니다

0203peter 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말