약 을 따다
1547 단어 알고리즘
입력 형식 입력 형식
첫 줄 은 두 개의 정수 T (1 & lt; T & gt; = 1000) 와 M (1 & gt; = M & gt; = 100) 로 나 뉘 어 져 있 으 며, T 는 모두 약 초 를 채취 할 수 있 는 시간 을 의미 하 며, M 은 동굴 안의 약초 의 수 를 나타 낸다. 다음 M 행 은 각각 1 ~ 100 사이 (1 과 100 포함) 의 정 수 를 포함 하여 어떤 약 초 를 채취 하 는 시간 과 이 약초 의 가 치 를 나타 낸다.
출력 형식 출력 형식
한 줄 을 포함 하여 이 줄 은 정 해진 시간 내 에 채취 할 수 있 는 약초 의 최대 총 가 치 를 나타 내 는 정수 만 포함 하고 있 습 니 다.
출력
시간: 1 초
/**
:
,
, 。
。
:
01
*/
#include
#include
using namespace std;
#define mNum 101
int time[mNum];
int value[mNum];
int best[mNum][mNum]; //best[i][j]: i j
int main()
{
int t,m;
cin>>t>>m; // ,
for(int i=1;i<=m;i++)
{
cin>>time[i]>>value[i];
}
memset(best,0,sizeof(best)); //
for(int i=1;i<=m;i++) //m
{
for(int j=1;j<=t;j++) //
{
best[i][j] = best[i-1][j];
if(j>=time[i])
best[i][j] = max(best[i-1][j],best[i-1][j-time[i]]+value[i]);
}
}
cout<
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.