連結ファイル11066

質問する

小説家の金大全は小説をいくつかの章(章)に分け、それぞれの章は異なる文書に保存されている.小説の各章を書き終えた後、各章に書かれた書類を統合し、最終的に小説の完成本を含む書類を形成する.この過程で、2つのファイルを1つの一時ファイルにマージし、これらの一時ファイルまたは元のファイルを2つのファイルにマージし続け、小説の複数の章を連続させ、最終的に1つのファイルにマージします.2つのファイルをマージするために必要なコスト(時間など)が2つのファイルサイズの合計であるとします.最終的なファイルを完了するために必要なコストの合計を計算します.
例えば、C 1、C 2、C 3、およびC 4は、それぞれ40、30、30、および50のファイルサイズの4章連続である.これらのファイルをマージする過程で、まずC 2とC 3を一時ファイルX 1にマージする.この場合、60元かかります.次に、C 1とX 1を組み合わせて一時ファイルX 2を作成するには100ドルが必要である.最終的に、X 2とC 4を組み合わせて最終ファイルを生成するには150ドルかかります.したがって、最終的なファイルの作成に要するコストの合計は、60+100+150=310です.他の方法でファイルをマージすると、コストを削減できます.まず、C 1とC 2を結合して一時ファイルY 1を作成し、C 3とC 4を結合して一時ファイルY 2を作成し、最後にY 1とY 2を結合して最終ファイルを作成する.この場合の総費用は70+80+150=300です.
小説の各章のファイルサイズが指定されている場合は、これらのファイルを1つのファイルにマージするために必要な最低コストを計算するプログラムを作成します.

入力

プログラムは標準入力から入力データを受信する.プログラムの入力はT個のテストデータからなり,Tは入力の第1行に与えられる.各試験データには2行が与えられ,1行目は小説を構成する章節数を表す正の整数K(3≦K≦500)を与えた.2行目には、1章からK章までの収録ファイルの大きさを表す正の整数Kが与えられる.ファイルサイズは10000を超えません.

しゅつりょく

プログラムは標準出力に出力されます.各テストデータは1行に正確に出力され、すべての章をマージするために必要な最小コストが出力されます.
https://www.acmicpc.net/problem/11066
次のような解答手順があります.
https://guy-who-writes-sourcecode.tistory.com/43参照.

全体的な概念はこうです.dp[i][j]の概念を確立し、
さらに一点を分割し、dp[i][x]+dp[x+1][j]=dp[i][j](x+i<=x<=j-1)で点火式を確立し、------(1)
点火式の内因性dp[i][i]とdp[i][i+1],dp[i][i+2]の間の計算式を確立した.
(dp[i][i+3]から(1)からdp[i][i+1]+dp[i+2][i+3]に変換し、Xを計算する必要がある)
dp[i][i]、dp[i][i+1]は簡単ですが、dp[i][i+2]は2つの計算のうちの1つで、ここでの共通点はiからi+2までの部分加算です.
したがって、sum[i]を定義し、sum[i+2]−sum[i−1]を部分的および計算する.
最終的な点火式は、dp[i][j]=(dp[i][j]または、dp[i][x]+dp[x+1][j]+sum[j]-sum[i-1]の最適値)である.
このセクションの説明については、次の図を参照してください.

import java.util.Scanner;

public class Main {
	static int dp[][];
	static int novel[];
	static int sum[];
	static int k;
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int t = scanner.nextInt();
		while (t > 0) { //모든 입력을 받는다.
			k = scanner.nextInt();
			//테스트 마다 초기화 진행
			dp = new int[k + 1][k + 1];
			novel = new int[k + 1];
			sum = new int[k + 1];
			for (int i = 1; i <= k; i++) {
				novel[i] = scanner.nextInt();
				sum[i] = sum[i - 1] + novel[i]; //i번째까지의 모든 비용의 합
				//부분합으로 사용할것임
			}
			algorithm1();
			t--;
		}
	}
	public static void algorithm1() {
		//sum에 저장된수로인해 dp가완성됨
		for (int n = 1; n <= k; n++) { 
			for (int i = 1; i + n <= k; i++) {
				int j = i + n;
				dp[i][j] = 214748364; 
				for (int x = i; x < j; x++) {
					//1회째는 dp초깃값인 int최대정수와 점화식을비교, 무조건 점화식의 값이 dp[i][j]
					//n회쨰는 dp[i][j] 기존값과 범위가달라진 점화식중 비교하여 최솟값이 dp[i][j]
					//모든 범위를 반복시 결국 가장최솟값이 dp[i][j]
					dp[i][j] = Math.min(dp[i][j],
							dp[i][x] + dp[x + 1][j] + sum[j] - sum[i - 1]);
				}
			}
		}
		System.out.println(dp[1][k]);
	}
}