동적 기획 - 한 줄 로 늘 어선 카드 게임 문제
2063 단어 알고리즘
수치 가 다른 카드 를 하나의 선 으로 배열 하 는 정형 배열 arr 를 지정 합 니 다.게이머 A 와 게이머 B 는 차례대로 모든 카드 를 가 져 가 고 게이머 A 가 먼저 가 져 가 고 게이머 B 가 나중에 가 져 가도 록 규정 하지만 모든 게이머 들 은 매번 가장 왼쪽 이나 가장 오른쪽 카드 만 가 져 갈 수 있 고 게이머 A 와 게이머 B 는 매우 똑똑 하 다.마지막 우승자 의 점 수 를 되 돌려 주세요.
[예 를 들 면]
arr=[1,2,100,4]。
시작 시 플레이어 A 는 1 또는 4 만 가 져 갈 수 있 습 니 다.게이머 A 가 1 을 가 져 가면 배열 이 [2, 100, 4] 로 바 뀌 고 그 다음 에 게이머 B 는 2 또는 4 를 가 져 간 다음 에 계속 게이머 A 차례 가 된다.시작 할 때 게이머 A 가 4 를 가 져 가면 배열 이 [1, 2, 100] 으로 바 뀌 고 그 다음 에 게이머 B 는 1 또는 100 을 가 져 간 다음 에 계속 게이머 A 차례 가 된다.게이머 A 는 가장 똑똑 한 사람 으로서 먼저 4 를 가 져 가지 않 습 니 다. 4 를 가 져 가면 게이머 B 가 100 을 가 져 가기 때 문 입 니 다.그래서 게이머 A 는 먼저 1 을 가지 고 배열 을 [2, 100, 4] 로 바 꾸 고 그 다음 에 게이머 B 는 어떻게 선택 하 든 100 은 게이머 A 가 가 져 갑 니 다.플레이어 A 가 승리 하고 점 수 는 101 입 니 다.그래서
arr=[1,100,2]。
시작 할 때 게이머 A 는 1 을 가 져 가든 2 를 가 져 가든 게이머 B 는 아주 똑똑 한 사람 으로서 100 을 가 져 간다.플레이어 B 가 승리 합 니 다. 점 수 는 100 입 니 다.그 러 니까 100 으로 돌아 가.
public class Problem_14_CardsInLine {
public static int win1(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
return Math.max(f(arr, 0, arr.length - 1), s(arr, 0, arr.length - 1));
}
public static int f(int[] arr, int i, int j) {
if (i == j) {
return arr[i];
}
return Math.max(arr[i] + s(arr, i + 1, j), arr[j] + s(arr, i, j - 1));
}
public static int s(int[] arr, int i, int j) {
if (i == j) {
return 0;
}
return Math.min(f(arr, i + 1, j), f(arr, i, j - 1));
}
public static int win2(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int[][] f = new int[arr.length][arr.length];
int[][] s = new int[arr.length][arr.length];
for (int j = 0; j < arr.length; j++) {
f[j][j] = arr[j];
for (int i = j - 1; i >= 0; i--) {
f[i][j] = Math.max(arr[i] + s[i + 1][j], arr[j] + s[i][j - 1]);
s[i][j] = Math.min(f[i + 1][j], f[i][j - 1]);
}
}
return Math.max(f[0][arr.length - 1], s[0][arr.length - 1]);
}
public static void main(String[] args) {
int[] arr = { 1, 9, 1 };
System.out.println(win1(arr));
System.out.println(win2(arr));
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
