쓰레기함정쓰레기함정쓰레기함정

제목.

카멘 농부 존이 매우 소중히 여기는 홀스틴 젖소 한 마리가 쓰레기 우물에 빠졌다.쓰레기우물은 농부들이 쓰레기를 버리는 곳으로 깊이가 D(2<=D<=100)D(2<=D<=100)D(2<=D<=100)피트 카르멘이 쓰레기를 쌓으려다 우물만큼 높이 쌓이면 우물 밖으로 빠져나갈 수 있다.또한 카멘은 쓰레기를 먹어서 자신의 생명을 유지할 수 있다. 모든 쓰레기는 먹거나 쌓을 수 있고 쓰레기를 쌓는 데 카멘의 시간이 걸리지 않는다. 만약에 카멘이 쓰레기가 버리는 시간 t(0

입력

첫 번째 행위는 2개의 정수, D D D와 G(1<=G <=100) G(1<=G <=100) G(1<=G<=100), G는 우물에 투입된 쓰레기의 수량을 두 번째로 G+1G+1 G+1줄에 세 개의 정수를 포함한다. T(0

출력

만약 카멘이 함정에서 기어나올 수 있다면, 전체를 출력하면 가장 먼저 언제 기어나올 수 있는지를 나타낸다.그렇지 않으면 출력 카드가 가장 오래 살아남을 수 있습니까?

샘플 가져오기

Rubbish.in
20 4
5 4 9
9 3 2
12 6 10
13 1 1

출력 예제

Rubbish.out
13

샘플 설명

카멘은 그녀가 받은 첫 번째 쓰레기를 쌓아 올린다. h e i g h t = 9 height=9 height=9 카멘은 그녀가 받은 두 번째 쓰레기를 먹어치우고 그녀의 생명을 10시간에서 13시간 카멘에 세 번째 쓰레기를 쌓아 올린다. h e i g h t = 19 height=19 height=19 카멘에 네 번째 쓰레기를 쌓아 올린다. h e i g h t = 20 height=20

문제풀이의 방향

이 문제는 DP로 하겠습니다.
만약 이 고도의 생명치가 이 쓰레기가 버려진 시간보다 작지 않다면
만약 높이 + 이 쓰레기의 높이가 d보다 작지 않으면 이 쓰레기를 버리는 시간을 출력합니다
그렇지 않으면 이 높이+이 쓰레기의 높이의 생명치=max(d~0의 생명치), 즉 쓰레기를 먹지 않고 그것을 쌓아 올린다. 이때 높이+=이 쓰레기의 높이
이 고도의 생명치 + = 이 쓰레기를 먹으면 증가하는 생명치, 즉 쓰레기를 먹는다. 이때 고도는 변하지 않는다
마지막으로 고도 0의 생명치를 출력, 살아남지 못하는 최장 시간

절차는 다음과 같다.

#include
#include
#include
#include

using namespace std;

int d, g, f[100001];

struct r
{
	int t, f, h;
}a[100001];

bool cmp(r x, r y)
{
	return x.t < y.t;
}

int main()
{
	scanf("%d%d",&d,&g);
	for(int i = 1; i <= g; ++i)
		scanf("%d%d%d",&a[i].t,&a[i].f,&a[i].h);
	sort(a + 1, a + 1 + g, cmp);
	f[0] = 10;
    for(int i = 1; i <= g; ++i)
      for(int j = d; j >= 0; --j)
        if(f[j] >= a[i].t)
        {
            if(j + a[i].h >= d)
            {
                cout<<a[i].t;
                return 0;
            }                                                                                 
            f[j + a[i].h] = max(f[j + a[i].h],f[j]);
            f[j] += a[i].f;
        }
    cout<<f[0];
	return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

[BOJ]11048(python)

python 풀이 DP를 이용해 풀이 보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서 고민을 했는데 이 문구 덕분에 DP 를 이용해 풀이할 수 있었다 뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다 코...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다