2018 미 단 평가 프로 그래 밍 문제 1 번
3482 단어 알고리즘
프로 그래 밍 의 첫 번 째 문제: 이 시퀀스 의 하위 문자열 과 K 의 배수 인 하위 문자열 의 길 이 를 지정 합 니 다. 중복 이 있 으 면 출력 최대 길이 입 니 다.예 를 들 어 서열 은 {1, 2, 3, 4, 5} k = 5 면 하위 문자열 과 5 의 배수 가 {2, 3}, {1, 2, 3, 4}, {1, 2, 3, 4}, {5} 이 고 이때 길이 가 가장 큰 것 은 5 이 므 로 출력 5.
처음에 이 문 제 를 보 았 을 때 내 머 릿 속 의 첫 번 째 반응 은 폭력 으로 모든 가능성 을 열거 해 서 는 안 되 고 반드시 시간 을 초과 할 것 이다!
그리고 머리 도 여기 멈 췄 어.현재 상태 가 이전 상태 와 밀접 한 관 계 를 가지 기 때문에 동적 계획 의 원리 로 해 야 한 다 는 것 을 알 고 있다.그러나 나 는 좌우 지침 방향 으로 계속 생각 했 더 니 시간 이 다 되 었 다.
목욕 을 하고 이 문 제 를 다시 생각해 보 니 정말 간단 하 다.
모든 꼬치 는 이전 꼬치 에서 첫 번 째 를 빼 는 것 으로 볼 수 있다.그리고 2 차원 배열 로 모든 문자열 의 합 을 기록 하면 이 문 제 를 해결 할 수 있다.
import java.util.Scanner;
public class Main {
static int[] a = null;
static int k = 0;
static int max = 0;
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
s.nextLine();
String[] c = s.nextLine().split(" ");
a = new int[c.length];
for (int i = 0; i < c.length; i++) {
a[i] = Integer.valueOf(c[i]);
}
k = Integer.valueOf(s.nextLine());
// Random random = new Random();
// a = new int[10 * 1000];
// for (int i = 0; i < 10 * 1000; i++) {
// a[i] = random.nextInt(500000);
// }
//
// k = 20000;
int[] dp = new int[a.length + 1];
for (int i = 0; i < a.length; i++) {
dp[0] = 0;
for (int j = i; j < a.length; j++) {
dp[j + 1] = dp[j] + a[j];
if (dp[j + 1] % k == 0) {
if (max < j - i+1) {
max = j - i+1;
}
}
}
}
System.out.println(max);
}
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
