NKOJ1066 굶주린 젖소 [DP]

문제 설명
John은 약간의 젖소를 키웠는데, 매일 저녁 젖소는 모두 먹이를 먹어야 한다.조건이 비교적 누추하기 때문에 반드시 모든 젖소가 음식을 먹을 수 있는 것은 아니다.젖소의 식사 방식은 다음과 같다. John은 m개의 식통(1<=m<=2000)이 있는데 각각 번호는 1...m.이 식통들은 번호에 따라 한 줄로 배열되었다.John은 젖소들을 몇 조로 나누어 젖소마다 항상 함께 식사를 하고, 젖소들은 스타트에서 end통에 있는 음식을 먹어야 한다고 요구한다.몇몇 그룹의 젖소가 같은 통에 있는 음식을 먹어야 하기 때문에 충돌이 생겼을 수도 있다. 이때 John은 그 중의 한 그룹의 요구를 만족시킬 수 있을 뿐이고 다른 그룹은 굶을 수밖에 없다.John은 당연히 젖소를 모두 굶기고 싶지 않기 때문에 그는 젖소들이 제기한 요구에 따라 그 중 일부 그룹의 요구를 만족시켜 가장 많은 식통을 젖소에게 먹게 하기를 바란다.이 어려운 문제가 John을 괴롭히고 있는데, 그는 너의 도움을 얻기를 바란다.
입력 형식
첫 번째 줄의 정수 n은 젖소의 조수를 나타낸다.(1<=n<=1000) 제2~n+1줄, 줄마다 두 개의 정수start와end로 한 조의 젖소가 제기한 요구를 묘사한다.
출력 형식
최대 몇 개의 식통이 식용될 수 있는지를 나타내는 정수

해법

제발 욕심을 부리지 마라!
가방 DP, f[i]는 앞의 i개의 식통 중 가장 많이 사용할 수 있는 식통의 수를 나타낸다.

코드

#include
#include
#include
using namespace std;
int f[2100];
struct node{int s,e;}in[1100];
int main(){
    int n,R=0;scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&in[i].s,&in[i].e);
        R=max(R,in[i].e);
    }
    for(int i=1;i<=R;i++){
        f[i]=f[i-1];
        for(int j=1;j<=n;j++)
            if(in[j].e<=i)f[i]=max(f[i],f[in[j].s-1]+in[j].e-in[j].s+1);
    }
    printf("%d",f[R]);
}

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

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

49일차 - 2022.04.20

Baekjoon에서 문제풀이 1) 문제 : 첫째 줄에는 별 1개, 둘째 줄에는 별 2개, N번째 줄에는 별 N개를 찍는 문제/ 첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다. 첫째 줄부터 N번째 줄까지 차례대로 별...

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

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

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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