UVA 507 - Jill Rides Again 동적 계획
4426 단어 동적 기획
Jill Rides Again
Jill likes to ride her bicycle, but since the pretty city of Greenhills where she lives has grown, Jill often uses the excellent public bus system for part of her journey. She has a folding bicycle which she carries with her when she uses the bus for the first part of her trip. When the bus reaches some pleasant part of the city, Jill gets off and rides her bicycle. She follows the bus route until she reaches her destination or she comes to a part of the city she does not like. In the latter event she will board the bus to finish her trip.
Through years of experience, Jill has rated each road on an integer scale of ``niceness.'' Positive niceness values indicate roads Jill likes; negative values are used for roads she does not like. There are not zero values. Jill plans where to leave the bus and start bicycling, as well as where to stop bicycling and re-join the bus, so that the sum of niceness values of the roads she bicycles on is maximized. This means that she will sometimes cycle along a road she does not like, provided that it joins up two other parts of her journey involving roads she likes enough to compensate. It may be that no part of the route is suitable for cycling so that Jill takes the bus for its entire route. Conversely, it may be that the whole route is so nice Jill will not use the bus at all.
Since there are many different bus routes, each with several stops at which Jill could leave or enter the bus, she feels that a computer program could help her identify the best part to cycle for each bus route.
Input
The input file contains information on several bus routes. The first line of the file is a single integer
b
representing the number of route descriptions in the file. The identifier for each route (
r
) is the sequence number within the data file,
. Each route description begins with the number of stops on the route: an integer
s
,
on a line by itself. The number of stops is followed by
s
- 1 lines, each line
i
(
) is an integer
n
i
representing Jill's assessment of the niceness of the road between the two stops
i
and
i
+1.
Output
For each route
r
in the input file, your program should identify the beginning bus stop
i
and the ending bus stop
j
that identify the segment of the route which yields the maximal sum of niceness, m= n
i
+n
i+1
+...+n
j-1
. If more than one segment is maximally nice, choose the one with the longest cycle ride (largest
j
-
i
). To break ties in longest maximal segments, choose the segment that begins with the earliest stop (lowest
i
). For each route
r
in the input file, print a line in the form:
The nicest part of route r is between stops i and j
However, if the maximal sum is not positive, your program should print:
Route r has no nice parts
Sample Input
3
3
-1
6
10
4
-5
4
-3
4
4
-4
4
-5
4
-2
-3
-4
Sample Output
The nicest part of route 1 is between stops 2 and 3
The nicest part of route 2 is between stops 3 and 9
Route 3 has no nice parts
제목:
버스 한 구간, 각 역은 하나, 둘, 셋...s, 각 역 사이의 경치 값은 다르다. 예를 들어 역 1에서 역 2까지의 경치 값은 5이고, 역 3에서 역 4까지의 경치 값은 -3이다.연속된 역의 경치 값의 합이 얼마나 되는지 구하세요.
분석:
최대 연속 서열, 길이가 같을 때 큰 것을 취하기;길이가 같으면 시작점이 가장 작은 것을 취한다.
#include<stdio.h>
#include<string.h>
int l[20005];
int main()
{
int b,n,i,max,sum,st,ed,cas=1,bg;
scanf("%d",&b);
while(b--)
{
scanf("%d",&n);
for(i=1;i<n;i++)
scanf("%d",&l[i]);
max=sum=l[1];
st=bg=ed=1; /* 1 */
for(i=2;i<n;i++)
{
if(sum<0)
{
sum=0;
st=i; /* */
}
sum+=l[i];
if(sum>max||sum==max&&i-st>ed-bg)
{
max=sum;
bg=st; /*bg */
ed=i;
}
}
if(max<=0)
printf("Route %d has no nice parts
",cas++);
else
printf("The nicest part of route %d is between stops %d and %d
",cas++,bg,ed+1);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
01 가방, 완전 가방, 다중 가방 dp(동적 기획 입문 dp)01 가방은 2진법으로 직접 표시할 수 있지만 데이터 양이 너무 많으면 시간을 초과하는 것이 폭력이다.01 가방의 사상은 바로 이 물품에 대해 내가 넣은 가치가 큰지 안 넣은 가치가 큰지 비교하여 방정식 f[i][v...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.