낙곡-[동적 기획]-친구의 숫자
제목 설명
한 무리의 큰 친구들(나이 15세 이상)이 있는데 그들은 각자 손에 숫자를 하나씩 들고 있다. 물론 이 숫자는 1위, 즉 0에서 9사이에 불과하다.모든 큰 친구의 점수는 그의 이전 최장 불하강 서열의 모든 수의 합이다.(이 서열은 반드시 그것을 끝으로 해야 한다!)만약 여러 개의 최장 하위 서열이 내려가지 않는다면, 번호 사전의 서열이 가장 작은 것을 찾으십시오.지금 당신에게 n명의 큰 친구, 그리고 그들 각자의 숫자를 알려줄 테니, 그들 각자의 점수를 구해 주세요.
입력 출력 형식
입력 형식:
입력 파일이 bignum입니다.in.
첫 번째 줄, 한 개의 숫자 n.
두 번째 줄은 n개의 수로 각각 모든 사람의 숫자를 나타낸다.
출력 형식:
출력 파일이 bignum입니다.out.
한 줄, n개의 수는 각각 모든 사람의 점수를 나타낸다.
출력 샘플 가져오기
샘플 입력 #1: 복사
【 1】
5
1 2 5 3 4
【 2】
5
1 7 5 9 6출력 예제 #1: 복사
【 1】
1 3 8 6 10
【 2】
1 8 6 17 12설명
[예제 해석 1]
다섯 명의 점수는 각각 (1),(1+2),(1+2+5),(1+2+3),(1+2+3)이다.
[예제 해석 2]
다섯 명의 점수는 각각 (1),(1+7),(1+5),(1+7+9){또 하나(1,5,9)},(1+5+6)이다.
[데이터 규모]
50%의 데이터에 대해 1≤n≤500;
80%의 데이터에 대해 1≤n≤1000;
100% 데이터의 경우 1≤n≤10000.
문제풀이: 가장 긴 상승자 서열 개조를 바탕으로 사전 서열의 최소를 요구한다. 바로 특정한 위치를 선택하기 전의 한 수는 이 위치에 가장 가까운 수이다. 예를 들어 예시 2, 7, 5, 9, 6을 입력하면 9라는 위치에서 1,7, 9라는 서열을 선택하고 1,5,9라는 서열을 선택하지 않는다. 제목의 뜻을 알 수 있다. 이어서 코드로 실현하면 된다.
import java.util.*;
/*
*
*/
public class test{
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int n=in.nextInt();
int[] a=new int[n+1];
for(int i=1;i<=n;i++) {
a[i]=in.nextInt();
}
int[] dp=new int[n+1];
int[] c=new int[n+1];
for(int i=1;i<=n;i++) {
dp[i]=1;
for(int j=1;j=a[j]) {
if(dp[i]이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
P1040 플러스 두 갈래 트리(트리 dp)제목 링크https://www.luogu.org/space/show?uid=45444제목 설명 n개의 노드를 설정한 두 갈래 트리의 중서는 (1,2,3,..., n)이고 그 중에서 숫자는 1,2,3,..., n은 노...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
