SDNUOJ 1045 스톤 결합 1(구간 동적 계획)
4520 단어 문제를 풀지 않으면 마음이 괴롭다.동적 기획
N더미의 돌들이 한 줄로 늘어서 있고 한 무더기의 돌들은 일정한 수량을 가지고 있다고 묘사한다.이제 N으로 돌을 쌓아 한 무더기로 만들어야 한다.합병의 과정은 매번 서로 인접한 두 무더기의 돌을 한 무더기로 쌓을 수 있을 뿐, 합병할 때마다 걸리는 대가는 이 두 무더기의 합이고 N-1번의 합병을 거쳐 한 무더기가 된다.총 대가의 최소치를 구하다.여러 그룹의 테스트 데이터를 입력하고 파일이 끝날 때까지 입력하십시오.각 그룹의 테스트 데이터 첫 줄에는 n의 정수 n이 있는데 n의 돌무더기가 있음을 나타낸다.다음 줄에는 n(0
3 1 2 3 7 13 7 8 16 21 4 18
샘플 출력
9 239
사고의 방향
만약 이 문제가 인접 합병을 요구하지 않았다면 이 문제는 전형적인 하프만 코딩 사상이다. 먼저 수량이 작은 돌을 합병하고 수량이 큰 돌을 마지막에 합병하면 마지막 대가가 가장 적다.대응하는 것은 하프만 트리의 구축 과정으로 이 알고리즘은 두 갈래 트리의 권한이 가장 우수함을 보장한다.
그러나 제목이 특별히 인접합병을 요구했다면 이 문제는 고전적인 구간 동태적 기획 문제로 바뀌었다.구간 동태 기획 문제의 전형적인 특징은 하나의 큰 구간의 최우선을 요구하고 큰 구간은 작은 구간에서 조합된 것이기 때문에 작은 구간이 최우선이라면 구성된 큰 구간도 반드시 최우선이다.예를 들어 우리가 [1,3] 사이의 최우선 합병을 요구한다면 [1,3]은 [1,1]과[2,3], 또는 [1,2]와[3,3]가 합병되어 올 수 있기 때문에 이 두 가지 상황의 최소치만 요구하면 된다.그래서 우리의 상태 이동 방정식은 다음과 같다.
dp[i][j]=0,i=j d p [ i ] [ j ] = 0 , i = j
dp[i][j]=min{dp[i][j],dp[i][k]+dp[k+1][j]+sum[i,j]} d p [ i ] [ j ] = m i n { d p [ i ] [ j ] , d p [ i ] [ k ] + d p [ k + 1 ] [ j ] + s u m [ i , j ] }
위의sum[i,j]는 구간 i에서 j까지의 돌의 수량을 나타낸다.왜냐하면 돌을 합병할 때 대가 = 두 구간 각자의 대가 + 이 두 구간 돌의 총량(즉 합병 후 i에서 j까지의 돌의 총량)은 여기에 3층 for순환이 있고 외층 통제 구간의 길이, 2층 통제 구간의 시작 위치, 최내층 통제 분할의 위치를 표시하면 된다.
코드
package com.special.NYOJ;
import java.util.*;
/**
* Created by Special on 2018/5/31 8:34
*/
public class NYOJ0737 {
static final int MAX = (int) 1e6;
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
while(input.hasNext()){
int n = input.nextInt();
int[] num = new int[n + 1];
int[] sum = new int[n + 1];
int[][] dp = new int[n + 1][n + 1];
for(int i = 0; i < n + 1; i++) {
Arrays.fill(dp[i], MAX);
}
for(int i = 1; i <= n; i++){
num[i] = input.nextInt();
sum[i] = sum[i - 1] + num[i];
dp[i][i] = 0;
}
int temp = 0;
for(int len = 1; len < n; len++){
for(int i = 1; i + len <= n; i++){
int j = i + len;
temp = sum[j] - sum[i - 1];
for(int k = i; k < j; k++){
dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + temp);
}
}
}
System.out.println(dp[1][n]);
}
}
}
넓히다
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
POJ3276-젖소 뒤집기Each time the machine is used, it reverses the facing direction of a contiguous group of K cows in the line (one cannot ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
