H - Roller Coaster
Bessie has gone on a trip, and she's riding a roller coaster! Bessie really likes riding the roller coaster, but unfortunately she often gets dizzy.
The roller coaster has a number of distinct sections that Bessie rides in order. At the beginning of the ride, Bessie's dizziness and fun levels are both at 0. For each section of the roller coaster, Bessie can either keep her eyes open or keep them closed (and must keep them that way for the whole section). If she keeps her eyes open for a section, her total fun increases by a Fun factor for that section, and her dizziness increases by a Dizziness factor for that section. However, if she keeps her eyes closed for the section, her total fun will not change, but her dizziness will decrease by a value that's constant for the entire roller coaster. (Note that her dizziness can never go below 0.)
If, at any point, Bessie's dizziness is above a certain limit, Bessie will get sick. Write a program to find the maximum amount of fun Bessie can have without getting sick.
Input
There will be several test cases in the input. Each test case will begin with a line with three integers:
N K L
Where N (1N1, 000) is the number of sections in this particular roller coaster, K (1K500) is the amount that Bessie's dizziness level will go down if she keeps her eyes closed on any section of the ride, and L (1L300, 000) is the limit of dizziness that Bessie can tolerate - if her dizziness ever becomes larger than L, Bessie will get sick, and that's not fun!
Each of the next N lines will describe a section of the roller coaster, and will have two integers:
F D
Where F (1F20) is the increase to Bessie's total fun that she'll get if she keeps her eyes open on that section, and D (1D500) is the increase to her dizziness level if she keeps her eyes open on that section. The sections will be listed in order. The input will end with a line with three 0s.
Output
For each test case, output a single integer, representing the maximum amount of fun Bessie can have on that roller coaster without exceeding her dizziness limit. Print each integer on its own line with no spaces. Do not print any blank lines between answers.
Sample Input
3 1 2
2 1
3 1
5 2
10 5 1
20 2
12 4
3 3
10 6
20 3
19 9
19 7
1 500
15 5
4 2
0 0 0
Sample Output
7
0
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define INF 0x7fffffff
#define MOD 10000000
#define N 1005
using namespace std;
int main()
{
int n,K,L,totF;
int F[N],D[N],f[2][200005];
while(scanf("%d%d%d",&n,&K,&L),n!=0 || K!=0 || L!=0)
{
totF=0;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&F[i],&D[i]);
totF+=F[i];
}
for(int i=0;i<=totF;i++)
f[1][i]=INF;
f[1][F[1]]=D[1]; f[1][0]=0;
for(int i=2;i<=n;i++)
{
f[i%2][0]=0;
for(int j=1;j<=totF;j++)
{
f[i%2][j]=INF;
if(f[(i-1)%2][j]<=L) f[i%2][j]=min(f[i%2][j],max(0,f[(i-1)%2][j]-K));
if(j-F[i]>=0 && f[(i-1)%2][j-F[i]]<=L) f[i%2][j]=min(f[i%2][j],f[(i-1)%2][j-F[i]]+D[i]);
}
}
int ans=0;
for(int i=1;i<=totF;i++)
if(f[n%2][i]<=L) ans=i;
printf("%d
",ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
cocos2d Lua 학습(一)ios에서 루아 함수 호출 및 전참 방법 lua 코드: 출력 결과: lua 호출 C++ 방법: add 함수: lua 코드: 출력 결과: 함수를 호출합니다. 함수를 호출하려면 다음 협의를 따르십시오. 우선, 호출할 함...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.