11066:ファイルのマージ

[伯俊]11066号書類を合わせて2ℋ

2022.02.08
この問題は、複数のファイルを「連続」にマージする必要があります.

問題を解く

ダイナミックプランニング法を使うべきだと考えるのは難しくない.絵を1枚描けばいい(以前の解答を参照)

dp[左][右]左から右の範囲のサブセットの最小値を設定します.

以前とは違う接着剤で解いて、もっと時間がかかりました.

import java.io.*;
import java.util.*;

public class Main{

    public static int[] input; // 현재 테스트의 input
    public static int k; // 현재 테스트의 장의 개수
    public static int[][] dp = new int[500][500];
    public static int[][] sumCache = new int[500][500];
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StringTokenizer st;
    public static void settingNSolve() throws IOException {
        int t = Integer.parseInt(br.readLine());

        // 각 테스트는 두 개의 행으로 주어진다.
        for(int i = 0 ; i < t ; i ++){
            // init
            k = Integer.parseInt(br.readLine());
            input = new int[k];
            // init dp
            for(int j=0;j<k;j++){
                Arrays.fill(dp[j],-1);
            }
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < k; j++) {
                input[j] = Integer.parseInt(st.nextToken());
                dp[j][j] = input[j];
                sumCache[j][j] = input[j];
            }
            // init sumCache
            sum();
            System.out.println(recur(0,k-1));
        }
    }
    public static int recur(int left, int right){

        if(dp[left][right]!=-1)return dp[left][right];

        //원소가 2개 인 경우
        if(right-left == 1){
//            System.out.println("[ "+left+","+right+" ] MIN : " +(input[left]+input[right]));
            return dp[left][right] = (input[left]+input[right]);
        }

        int tempSum = 0, min = Integer.MAX_VALUE;
        for(int i = left+1;i <= right;i++){
            tempSum = recur(left,i-1);
            tempSum += recur(i,right);
            // 범위 길이가 1보다 크면 sum 을 더해줘야할 듯!!!!!
            if( i-1-left > 0) tempSum += sumCache[left][i-1];
            if( right - i > 0) tempSum += sumCache[i][right];
            min = Math.min(min,tempSum);
        }
//        System.out.println("[ "+left+","+right+" ] MIN : " +(min));
        return dp[left][right] = min;
    }
    public static void sum(){
        for(int l = 0 ; l<k;l++){
            for(int r = l+1; r<k;r++){
                sumCache[l][r] = sumCache[l][r-1] + input[r];
            }
        }

    }

    public static void main(String[] args) throws IOException{
        settingNSolve();

    }
}

改善

以前の解答の仕方を読み直す.

段に分けて再帰的に実行し,重複する部分→動的計画法を実行する.

もし、初めて思ったように、左から右の区間をサブLとサブRに分けて再帰(左,i-1)+recur(i,右)し、和(左,右)を求めるためには、サブセットで、個数が1つしかない場合を考慮しなければならない.(a 1+a 2)+a 3であれば、解くにはa 1+a 2+a 3+(a 1+a 2)が必要です.この時a 3は二度と変わる子供ではないからだ.

今回の解の時の私は、サブセットで、1つの要素のみからなるサブセットであればsumのオブジェクトには含まれません.

このようにして、毎回サブセットのサイズをチェックし、これに基づいて和を求める.

の前に、dpを解放する方法は、dpのすべての値を-1に設定するが、dp[k][k]=0を先に設定する必要がある.この場合、recur(左、左)はsum(左、右)でa 3を追加できるため、0を返します.

また、2つの要素のみからなる左右の範囲であればrecurを呼び出すとき!

dp非-1値の有無

-1の場合、2つの要素の和をdpに設定して戻ります.
彼に任務を遂行させる.
これにより、recurが呼び出されるたびにチェックされるif文が追加されます.
2つの要素のみからなるサブセットの値については、dpを初期に設定できます.

初回コミット時にタイムアウトが発生しました.

.しかし間違っているのでsum(left,right)を計算するのは負担だと思いますので、まずbottomup方式でsumcache[left][right]を埋めてから使います.

以前の解答と今回の解答を合わせてもう一度提出します.

より前のプールに+sumがキャッシュされ、使用値が少し速くなりました.

常にleft<=rightに設定されているためsumcacheの初期化が実現され、以下に示す

import java.io.*;
import java.util.*;

public class Main{

    public static int[] input; // 현재 테스트의 input
    public static int k; // 현재 테스트의 장의 개수
    public static int[][] dp = new int[500][500];
    public static int[][] sumCache = new int[500][500];
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StringTokenizer st;
    public static void settingNSolve() throws IOException {
        int t = Integer.parseInt(br.readLine());

        // 각 테스트는 두 개의 행으로 주어진다.
        for(int i = 0 ; i < t ; i ++){
            // init
            k = Integer.parseInt(br.readLine());
            input = new int[k];
            // init dp : 기본값 -1 , [i][i] 는 0 을 세팅 
            for(int j=0;j<k;j++){
                Arrays.fill(dp[j],-1);
            }
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j  <k; j++) {
                input[j] = Integer.parseInt(st.nextToken());
                dp[j][j] = 0;
                sumCache[j][j] = input[j];
            }
            // 원소가 2개인 경우 dp 에 미리 세팅하기 
            for(int l = 0; l < k-1;l++){
                dp[l][l+1] = input[l] + input[l+1];
            }
            // init sumCache
            initSumCache();
            // solve
            System.out.println(recur(0,k-1));
        }
    }
    public static int recur(int left, int right){
        if(dp[left][right]!=-1) return dp[left][right];
        int min = Integer.MAX_VALUE;
        for(int i = left+1;i <= right;i++){
            min = Math.min(min, recur(left,i-1)+recur(i,right));
        }
        min += sumCache[left][right];
        return dp[left][right] = min;
    }
    public static void initSumCache(){
        for(int l = 0 ; l<k;l++){
            for(int r = l+1; r<k;r++){
                sumCache[l][r] = sumCache[l][r-1] + input[r];
            }
        }
    }
    public static void main(String[] args) throws IOException{
        settingNSolve();
    }
}

[伯俊]11066号書類を合わせて1ℋ

両ファイルのマージ→テンポラリファイルの生成

ファイルを次のように結合します.

ファイル+一時ファイル

ファイル+ファイル

テンポラリファイル+テンポラリファイル

このときこのように加算すると[連続加算]が要求される.

最終的にファイルを完了するのにかかる費用の合計を計算したいです.

例について

C1 C2 C3 C4
40 30 30 50 

C2 + C3 = X1 = 60
C1 + X1 = X2 =40 + 60 = 100
C4 + X2 = 50 + 100 = 150
또는 
C1+ C2 = Y1 = 70
Y1 + C3 = Y2 = 70 + 30 = 100
C4 + Y2 = 100 + 50 = 150 

解法(正しいですが、最も時間がかかる方法のようです)

プルはDPを使うべきだと思っています.

分割征服に似た分割方式を考えたことがある.

自然に重なる区間がたくさんあるのでDPを考えたら

隣り合ってこそできる.
各

テストは500枚あります.

順序も重要です

a 1 a 2 a 3 a 4時

a2+a3 → b1

b1 + a4 (+ b1 ) = b2

分割征服方式を用い,遡及法を用いることはできず,

.

backtrackingは最後です

必要なのは、ある和を返し、コンポーネント1とコンポーネント2

を返すことです.

つまり遡及王ではない

2つの章があれば
→あと2つ加えればいい.
3つ以上の章
a1 a2 a3
a1+ a2 = b1
b1 + a3
そのうち銀→a 1+a 2+b 1+a 3
いくつかの関数では、
区間全体を→section 1、section 2に分けます.→section 1+section 2に戻ります.

左、右が存在する場合は、区間を区切るピボット

があるようにしてみる.

ピボット左≦ピボット<右

段は、[左~ピボット],[ピボット+1~右]である.

if : right

特定領域を分割する場合は様々であるが,最終的には1つのpivotを基準に左〜pivotとpivot+1〜右に分かれる.
これは、要素1で除算してマージするプロセスです.
いずれにしてもsectionの値は「最小値」です
計算

divideの節の最小値を求め、分割された木に沿って上へ進む.

import java.io.*;
import java.util.*;

public class Main{
    // dp 를 사용해야한다. divide 시켜놓고 합할 건데, 각 부분들은 최소 값을 갖도록 해야한다
    // 여기서 최소값은, a + b  = A , c + A = B 일 때, a + b + c + A 도 최소.. B도 최소여야하지 않나........
    // 근데 a + b + c + A가 최소면 B도 최소네
    // 아무튼 recur이 리턴해야하는 것은 무엇일까? 아니, 리턴을 해야하는걸까?
    // 현재 상황의, 현재까지 더한 값 : dp[left][i] + dp[i+1][right] + dp[left]
    public static int[][][] dp = new int[500][500][2]; // dp[left][right][0] : 여기까지 오는데 필요한값 dp[left][right][1] 은 리턴값
    // 현재 주어진 챕터
    public static int[] cur = new int[500] ;
    // 현재 주어진 챕터의 수
    public static int k;
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StringTokenizer st;

    public static void setting() throws IOException{
        int t = Integer.parseInt(br.readLine());
        for(int i =0; i<t; i++){
            // 각 테스트
            k = Integer.parseInt(br.readLine());
            // input
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<k;j++){
                cur[j] = Integer.parseInt(st.nextToken());
            }
            // dp init
            init(k);
            recur(0,k-1);
            System.out.println(dp[0][k-1][0]);

        }

    }
    /*
    * 각 파일의 크기는 양의 정수로 주어지기 때문에 dp 값을 0으로 설정해도 될 듯
    * */
    public static void init(int k){

        for( int r=0; r<k;r++){
            for(int c=0;c<k;c++){
                dp[r][c][0] =0;
                dp[r][c][1] =0;
            }
            dp[r][r][1] = cur[r];
        }
    }

    // 현재까지오는데 더한 값 -> 현재 값은 포함하지 않음
    // 두 개의 원소로 이루어진 경우에는 -> [0]과 [1]이 같을 수 밖에
    // 좌측부분 까지 가는데 필요한 값을 dp[left][right][0] 을 통해 얻을 수 있다
    // 좌측에서 리턴되는 값은, 그냥 값...
    public static void recur(int left, int right){
        // return 값, 여기까지 오는데 필요한 값 을 구분하여 저장하도록 하자
        if(dp[left][right][1] != 0){
            return;
        }
        // 만약 right = left + 1 이라면 ?
        int minSum = Integer.MAX_VALUE;
        int min = Integer.MAX_VALUE;

        int curSum = 0,cur=0;
        for(int i =left;i<right;i++){
            recur(left,i);
            recur(i+1,right);
            curSum = 0;
            curSum += dp[left][i][0];
            curSum += dp[i+1][right][0];
            curSum += dp[left][i][1];
            curSum += dp[i+1][right][1];

            if(curSum < minSum ){
                minSum = curSum;
                min = dp[left][i][1] + dp[i+1][right][1];
            }
        }
        dp[left][right][0] = minSum;
        dp[left][right][1] = min;

    }

    public static void main(String[] args) throws IOException{

        setting();

    }
}

プールの改良

上記の解答では,dpを3次元に設定する必要はない.

は現在dpを2次元としている.

は、dp[左][右]において左から右のファイルの合計である.すなわち,上記プールのdp[left][right][0]値のみをdpとする.

、すなわち左=右の場合は0.

の上の解答では、私がdp[左][right][0]=0をしたのと同じです.

分割部分に2つの要素しかない場合は、予め値を設定してください.

dp[left][left+1] = cur[left] + cur[left+1]

そして私が混乱している部分はこれです.💥💥問題そのものに対する理解が足りないから

recur(左、右)においてi単位で分割する場合、

で割る部分については、現在、評価時に

である.

dp[left,i]+dp[i+1,right]と(left~i)セグメントのすべてのファイルに1つの値を追加し、(i~right)セグメントのすべてのファイルに1つの値を追加します!もともとそうだった.

ファイルを左から右に加算すればいい

dp[left,i ] + dp[i+1,right ] + totalsum(left,right)

import java.io.*;
import java.util.*;

public class Main{
    // dp 를 사용해야한다. divide 시켜놓고 합할 건데, 각 부분들은 최소 값을 갖도록 해야한다
    // 여기서 최소값은, a + b  = A , c + A = B 일 때, a + b + c + A 도 최소.. B도 최소여야하지 않나........
    // 근데 a + b + c + A가 최소면 B도 최소네
    // 아무튼 recur이 리턴해야하는 것은 무엇일까? 아니, 리턴을 해야하는걸까?
    // 현재 상황의, 현재까지 더한 값 : dp[left][i] + dp[i+1][right] + dp[left]
    public static int[][] dp = new int[500][500]; // dp[left][right][0] : 여기까지 오는데 필요한값 dp[left][right][1] 은 리턴값
    // 현재 주어진 챕터
    public static int[] cur = new int[500] ;
    // 현재 주어진 챕터의 수
    public static int k;
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StringTokenizer st;

    public static void setting() throws IOException{
        int t = Integer.parseInt(br.readLine());
        for(int i =0; i<t; i++){
            // 각 테스트
            k = Integer.parseInt(br.readLine());
            // input
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<k;j++){
                cur[j] = Integer.parseInt(st.nextToken());
            }
            // dp init
            init(k);
            System.out.println(recur(0,k-1));
        }
    }
    /*
    * 각 파일의 크기는 양의 정수로 주어지기 때문에 dp 값을 0으로 설정해도 될 듯
    * */
    public static void init(int k){
        for(int r=0;r<k;r++){
            for(int c=0;c<k;c++){
                dp[r][c] = -1;
            }
            dp[r][r] = 0;
        }
        for(int r=0;r<k-1;r++) dp[r][r+1] = cur[r]+cur[r+1];
    }

    // 현재까지오는데 더한 값 -> 현재 값은 포함하지 않음
    // 두 개의 원소로 이루어진 경우에는 -> [0]과 [1]이 같을 수 밖에
    // 좌측부분 까지 가는데 필요한 값을 dp[left][right][0] 을 통해 얻을 수 있다
    public static int recur(int left, int right){
        // return 값, 여기까지 오는데 필요한 값 을 구분하여 저장하도록 하자
        if( dp[left][right] != -1){
            return dp[left][right];
        }
        int sum = Integer.MAX_VALUE ;
        for(int i= left;i<right;i++){
            sum = Math.min(sum,recur(left,i)+recur(i+1,right));
        }
        // left ~ right 파일 합
        for(int i = left; i <= right ; i++){
            sum += cur[i];
        }
        dp[left][right] = sum;
        return sum;
    }

    public static void main(String[] args) throws IOException{
        setting();
    }
}