글 읽기 - <다이어트> 반례 부탁드립니다 100%에서 틀렸습니다라고 나옵니다!

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(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<<' ';
		}
	}
}

seungchan0325 2년 전 0

어떻게 해결했는지 여쭤봐도 될까요?

#include <iostream>
#include <vector>
#include <limits>
#include <string>

using namespace std;

struct nut {
    int p, f, s, v, cost;
    nut operator+(nut a) {
        nut tmp;
        tmp.p = p + a.p;
        tmp.f = f + a.f;
        tmp.s = s + a.s;
        tmp.v = v + a.v;
        tmp.cost = cost + a.cost;
        return tmp;
    }
};

int n, min_cost = numeric_limits<int>::max();
nut min_nut;
vector<int> added;    

vector<nut> costes;

void f(int idx, nut total, vector<int> cur) {
    if(idx == n) {
        if((total.p >= min_nut.p) && (total.f >= min_nut.f) &&
           (total.s >= min_nut.s) && (total.v >= min_nut.v) && (total.cost < min_cost)) {
            min_cost = total.cost;
            added = cur;
        }
        return;
    }

    cur.push_back(idx+1);
    f(idx+1, total+costes[idx], cur);
    cur.pop_back();
    f(idx+1, total, cur);
}

int main() {
    cin >> n;
    cin >> min_nut.p >> min_nut.f >> min_nut.s >> min_nut.v;

    costes.resize(n);
    for(auto& i : costes)
        cin >> i.p >> i.f >> i.s >> i.v >> i.cost;

    f(0, nut{0, 0, 0, 0, 0}, vector<int>());
    if(min_cost == numeric_limits<int>::max())
        cout << -1;
    else {
        cout << min_cost << "\n";
        for(auto& i : added) 
            cout << i << " ";
    }
}

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

문제

문제

출처

ICPC

<다이어트> 반례 부탁드립니다 100%에서 틀렸습니다라고 나옵니다!

0203peter 2년 전 0

seungchan0325 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말