게임 이론 의 2 인 취 수 게임 에 대한 상세 한 설명
1973 단어 알고리즘
다음 과 같은 2 인용 게임 이 있 습 니 다. N (2 < = N < = 100) 개의 정수 서열 은 한 게임 플랫폼 에 놓 여 있 습 니 다. 게임 은 게이머 1 부터 시작 합 니 다. 두 사람 은 돌아 가면 서 서열 의 양 끝 에서 수 를 뽑 습 니 다. 수 를 뽑 은 후에 이 숫자 는 제거 되 고 본 게이머 의 득점 에 누적 되 었 습 니 다. 수 를 다 뽑 았 을 때 게임 은 묶 입 니 다.최종 득점 다 자로 이기다.
가장 좋 은 전략 을 실행 하 는 프로그램 을 만 듭 니 다. 가장 좋 은 전략 은 게이머 들 이 가장 좋 은 상대 와 대국 할 때 현재 상황 에서 가장 가능 한 총 점 전략 을 얻 을 수 있 도록 하 는 것 입 니 다.당신 의 프로그램 은 항상 두 번 째 유 저 를 위해 최 적 화 된 전략 을 실행 해 야 합 니 다.
격식.
PROGRAM NAME: game1
INPUT FORMAT:
(file game1.in)
첫 번 째 줄: 정수 N 은 시퀀스 의 정수 개 수 를 나타 낸다.
두 번 째 줄 에서 끝까지: 빈 칸 으로 구 분 된 N 개의 정수 (크기 는 1 - 200).
OUTPUT FORMAT:
(file game1.out)
한 줄 만 있 고 빈 칸 으로 구 분 된 두 개의 정수: 유저 1 과 유저 2 의 최종 득점 순 으로 나 뉜 다.
SAMPLE INPUT
6
4 7 2 9 5 2
SAMPLE OUTPUT
18 11사고: 재 귀 를 사용 하면 선명 하 게 보이 고 dfs 방법 을 정의 하 며 구간 ns 제 i 에서 j 번 째 수의 최대 치 를 되 돌려 줍 니 다.
여기 서 나 는 단순히 재 귀 해서 스스로 기억 배열 을 하나 더 해서 효율 을 높 일 수 있다.
public class {
static int[][] sum = new int[1000][1000];// ns ，sum[0][3] 0 3
static int[] ns = new int[]{4,7,2,9,5,2};//
/* ： ns i j */
static int dfs(int i,int j){
if (i==j) {// ，
return ns[i];
}
if (Math.abs(i-j)==1) {// ，
return Math.max(ns[i],ns[j]);
}
/* ， ，
sum[i+1][j] - dfs(i+1, j)+ns[i]
sum[i][j-1] - dfs(i, j-1)+ns[j]
， - +
*/
return Math.max(sum[i+1][j] - dfs(i+1, j)+ns[i], sum[i][j-1] - dfs(i, j-1)+ns[j]);
}
// sum
static void initSum(){
for (int i = 0; i < ns.length; i++) {
int tmp = 0;
for (int j = i; j < ns.length; j++) {
tmp += ns[j];
sum[i][j] = tmp;
}
}
}
public static void main(String[] args) {
initSum();
System.out.println(dfs(0, 5)+" " + (sum[0][5]-dfs(0, 5)));
}
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
