쓰레기 함정 codevs1684

3593 단어 dp

제목 설명Description


카멘 농부 존이 매우 소중히 여기는 홀스틴 젖소 한 마리가 쓰레기 우물에 빠졌다.쓰레기 우물은 농부들이 쓰레기를 버리는 곳으로 깊이가 D(2<=D<=100)피트이다.
카멘은 쓰레기를 쌓아 두려고 했는데, 우물과 같이 높이 쌓일 때까지 기다렸다가, 그녀는 우물 밖으로 도망갈 수 있었다.또 카멘은 쓰레기를 먹어서 자신의 생명을 유지할 수 있다.
모든 쓰레기는 먹거나 쌓아 놓을 수 있고 쓰레기를 쌓아 놓는 데 카드가 걸리지 않는다.
가령 카멘이 모든 쓰레기가 버리는 시간 t(0<=t<=1000)와 모든 쓰레기가 쌓인 높이 h(1<=h<=25)와 이 쓰레기를 먹으면 생명을 유지할 수 있는 시간 f(1<=f<=30)를 미리 알고 있다면 카멘이 가장 먼저 우물 밖으로 탈출할 수 있는 시간을 요구하고 카멘의 현재 체내에 10시간 동안 충분한 에너지가 있다고 가정하면 카멘이 10시간 동안 음식을 먹지 않으면 카멘은 굶어 죽을 것이다.

설명 입력 Input Description


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

출력 설명 Output Description


만약 카멘이 함정에서 기어나올 수 있다면, 전체를 출력하면 가장 먼저 언제 기어나올 수 있는지를 나타낸다.그렇지 않으면 출력 카드가 가장 오래 살아남을 수 있습니다.
샘플 입력 Sample Input 20 4
5 4 9
9 3 2
12 6 10
13 1 1
샘플 출력 Sample Output 13

데이터 범위 및 프롬프트 Data Size & Hint


[샘플 설명]
카멘은 그녀가 받은 첫 번째 쓰레기를 쌓아둔다:height=9;
카멘은 그녀가 받은 두 번째 쓰레기를 먹어서 그녀의 생명을 10시간에서 13시간으로 연장시켰다.
카멘에 세 번째 쓰레기를 쌓아두고,height=19;
카멘은 네 번째 쓰레기를 쌓아두고,height=20.
보기에는 매우 복잡해 보이지만, 사실은 매우 간단하다.
#include//dp[j]   j          ; 
#include//        dp[0]          ; 
#include
#include
using namespace std;
struct hh
{
    int t,h,f;
}a[10001];
int dp[10001],d,n;
bool cmp(hh a,hh b)
{
    return a.tvoid solve()
{
    cin>>d>>n;
    for(int i=1;i<=n;i++) scanf("%d%d%d",&a[i].t,&a[i].f,&a[i].h);
    dp[0]=10;
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        for(int j=d;j>=0;j--)
        {
            if(dp[j]>=a[i].t)
            {
                if(j+a[i].h>=d) cout<exit(0);
else {
dp[j+a[i].h]=max(dp[j+a[i].h],dp[j]);
dp[j]+=a[i].f;
}
}
}
}
cout<0]<int main()
{
solve();
return 0;
}

문제풀이를 보자마자 dp는 아직도 많이 연습해야 한다는 것을 깨달았다.
빙산 (백준 2573번 파이썬)
Beautifulsoup 및 Fast API를 사용하여 웹 사이트를 API로 변환

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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