hdu 1231 최대 연속 서브 시퀀스 DP
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 20633 Accepted Submission(s): 9151
Problem Description
K 개의 정수 서열{N1,N2,...,NK}을 지정 합 니 다.임의의 연속 하위 서열 은{Ni,Ni+1,...로 표시 할 수 있 습 니 다.
Nj},그 중 1<=i<=j<=K.최대 연속 서브 시퀀스 는 모든 연속 서브 시퀀스 에서 요소 와 가장 큰 것 입 니 다.
예 를 들 어 주어진 시퀀스{-2,11,-4,13,-5,-2}의 최대 연속 서브 시퀀스 는{11,-4,13}이 고 최대 와
되다
올해 데이터 구조 시험지 에 서 는 프로그램 작성 이 가장 큰 것 을 요구 합 니 다.지금 은 출력 이 필요 합 니 다.
하위 시퀀스 의 첫 번 째 와 마지막 요소.
Input
테스트 입력 은 몇 가지 테스트 용례 를 포함 하고 모든 테스트 용례 는 2 줄 을 차지 하 며,첫 번 째 줄 은 정수 K(<10000)를 제시 하고,두 번 째 줄 은 K 개의 정 수 를 제시 하 며,중간 은 빈 칸 으로 구분한다.K 가 0 일 때 입력 이 끝나 면 이 용례 는 처리 되 지 않 습 니 다.
Output
모든 테스트 사례 에 대해 1 줄 에서 최대 와 최대 연속 서브 시퀀스 의 첫 번 째 와 마지막 원 을 출력 합 니 다.
소,중간 에 빈 칸 으로 구분 합 니 다.최대 연속 서브 시퀀스 가 유일 하지 않 으 면 출력 번호 i 와 j 가 가장 작은 것(예 를 들 어 입력 사례 의 2,3 조)입 니 다.모든 K 개의 요소 가 음수 라면 최대 와 0 으로 정의 하고 전체 시퀀스 의 첫 번 째 요 소 를 출력 합 니 다.
Sample Input
6
-2 11 -4 13 -5 -2
10
-10 1 2 3 4 -5 -23 3 7 -21
6
5 -8 3 2 5 0
1
10
3
-1 -5 -2
3
-1 0 -2
0
Sample Output
20 11 13
10 1 4
10 3 5
10 10 10
0 -1 -2
0 0 0
Hint
Hint
Huge input, scanf is recommended.
hdu 1003 。。 dp, 1003 ， so easy ，
#include <stdio.h>
int main()
{
int n ;
while(scanf("%d",&n)!= EOF && n)
{
int ans = 0 , sum = 0 , first = 0 , last = 0 , start=0 , end=0 ;
int flag = 0 , head , tail;
for(int i = 0 ; i < n ; ++i)
{
int temp ;
scanf("%d",&temp) ;
if(temp<0)
{
if(i == 0)
{
head = temp ;
}
if(i == n-1)
{
tail = temp ;
}
++flag ;
}
if(sum == 0 && temp >= 0 )
{
start = temp ;
}
sum += temp ;
if(sum>ans)
{
ans = sum ;
last = temp ;
first = start ;
}
if(sum<0)
{
sum = 0 ;
}
}
if(flag!=n)
printf("%d %d %d
",ans,first,last) ;
else printf("%d %d %d
",ans,head,tail) ;
}
return 0 ;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
