로곡 P1048 채약(DP, 0-1 가방)

1593 단어 dpDP

로곡 P1048 채약(DP, 0-1 가방)


제목 설명

진진은 타고난 총명한 아이로 그의 꿈은 세계에서 가장 위대한 의사가 되는 것이다.그래서 그는 근처에서 가장 명망이 높은 의사를 스승으로 모시고 싶었다.의사는 그의 자질을 판단하기 위해 그에게 어려운 문제를 하나 냈다.의사는 그를 약초가 널려 있는 동굴로 데리고 가서 말했다. "얘야, 이 동굴에는 다른 약초가 있어. 한 그루씩 따는 데 시간이 좀 걸려. 한 그루마다 가치가 있어. 내가 시간을 줄게. 그 동안 약초를 따도 돼. 똑똑한 아이라면 채취한 약초의 총 가치가 가장 클 거야."
만약 네가 진진이라면, 너는 이 임무를 완성할 수 있니?

입력 출력 형식


입력 형식:

입력 파일 medic.첫 줄에는 두 개의 정수 T(1<=T<=1000)와 M(1<=M<=100)이 있는데 한 칸으로 나누면 T는 모두 약을 채취할 수 있는 시간을 대표하고 M은 동굴 안의 약초의 수를 대표한다.다음 M행은 줄마다 1에서 100 사이(1과 100 포함)의 정수 두 개를 포함하여 각각 어떤 약초를 따는 시간과 이 약초의 가치를 나타낸다.

출력 형식:

출력 파일 medic.out는 한 줄을 포함하고 이 줄은 하나의 정수만 포함하며 규정된 시간 안에 채취할 수 있는 약초의 최대 총 가치를 나타낸다.

출력 샘플 가져오기


샘플 #1 입력:

70 3
71 100
69 1
1 2

샘플 내보내기 #1:

3

설명

30% 데이터의 경우 M <= 10;
모든 데이터에 대해 M <= 100.
NOIP2005 보급팀 세 번째 문제

문제 풀이 분석


0-1 가방 문제, 동적 기획 방법으로 해답을 구합니다.
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
#define M 102
int t, m, ti[M], pr[M], f[1002];

void get_i(int &x){
	char ch = getchar();
	x = 0;
	while(!isdigit(ch)) ch = getchar();
	while(isdigit(ch)){
		x = x * 10 + ch - '0';
		ch = getchar();
	}
}
 
int main(){
	ios::sync_with_stdio(false);
	int i, j;
	get_i(t), get_i(m);
	for(i=1; i<=m; i++){
		get_i(ti[i]), get_i(pr[i]);
	} 
	for(i=1; i<=m; i++)
		for(j=t; j>=ti[i]; j--){
			f[j] = max(f[j], f[j-ti[i]]+pr[i]);
		}
	cout<
DRF - Tutorial 2
Amazon CloudFront & Lambda@Edge응답 바디 변경

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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