[アルゴリズムの問題を解く]白準10653マラソン2

24228 ワード
boj Java DP ps algorithm テキストリンク
今日解決される問題は、符号化リポジトリで毎日ランダムに数字を生成する白駿10653マラソン2である.
金貨の4つの問題、解いた後にとても簡単な問題、お疲れ様でしたううう、あれはとても難しいでしょう.解決すれば簡単な問題になるでしょう...
質問する
農場の乳牛が健康ではないと判断した農夫のジョンは、乳牛たちのためにマラソンを開催し、農夫のジョンにかわいがられている乳牛の朴勝元も参加する.
マラソンコースはN(3<=N<=500)個のチェックポイントからなり、1番のチェックポイントから順番にすべてのチェックポイントを訪問し、N番のチェックポイントで終了するとマラソンは終了します.怠惰な乳牛の朴勝元は本当に試合に参加するので、面倒だと思って、真ん中のK個のチェックポイントをこっそり飛び越えようとした.(K乳牛の朴勝元が最大K個のチェックポイントを飛び越えることができれば、勝元が走る最小距離はどのくらいなのだろうか.
ちなみに、乳牛マラソンはソウル都心で行われるため、距離はタクシー距離(Manhattan Distance)で計算される.すなわち、(x 1,y 1)と(x 2,y 2)点との距離は、|x 1−x 2|+|y 1−y 2|で表すことができる.(|x|は節値記号です.)
入力
1行目には、チェックポイント数Nとスキップするチェックポイント数Kが与えられる.
その後、N行ごとに2つの整数があります.i行目の1番目の整数は検査点iのx座標であり、2番目の整数はy座標である.(-1000 <= x <= 1000, -1000 <= y <= 1000)
チェックポイントの座標が重なる可能性があります.乳牛の朴勝元がチェックポイントをスキップすると、その番号のチェックポイントだけをスキップし、そのポイントのすべてのチェックポイントをスキップしません.
しゅつりょく
乳牛のパク・スンウォンはK個のチェックポイントを飛び越え、走ることができる最小距離をプリントアウトした.
例
入力します.
5 2
0 0
8 3
1 1
10 -5
2 2
出力します.
4
解答方法
実は私は何度か似たような問題をしたことがあります.このうち、最大/最小数を選択し、最小/最大数を作成します.
解法の結論を出す限りdpで解き,dp[k][n]に格納された値はn番目の座標に到達したとき,その前にk個をスキップしたときに格納される最小距離である.dpは、どの値を格納するかだけでなく、格納された値をどのように利用して計算を減らすかです.2回スキップして現在のn番目の座標の最小値を取得したい場合は、以下の3つの状況で各値を求め、その最小値を保存することができます.

  • n-1～2回スキップ時の最小値+n-1～nの距離
    n-1まで2回スキップしました(n-1以前の座標のいずれかをスキップしたのはわかりませんが、すべての場合最小値が保存されています).n-1はスキップされていない値で、前の座標から現在までの距離だけ増加します.

  • n-2から1にジャンプしたときの最小値+n-2とnの距離
    n-2は1回スキップされました(n-2以前の座標のいずれかをスキップしたが、すべての場合最小値が保存されています).n-2はスキップしていない値を求めたもので、現在は2回スキップしている場合なので、n-1をスキップしなければならないので、n-2から弦座標までの距離を増やすだけです.

  • n-3から0回の最小値+n-3とnの距離をスキップ
    一度もn-3をスキップしていない値が求められており、現在2回スキップしている場合は、n-1,n-2をスキップしなければならないので、n-3から弦座標までの距離を増やすだけです.
    • 上記の内容によって、点火式を表現できるはずです.
    dp[k][n] = 0<=i<=k 일 때, dp[k-i][n-i-1] + distance(n-i-1, n)들 중 최소값
    また、3番目の座標の値を求めることは、既に2回スキップしている場合は不可能であるため、計算を必要とせず、条件省略演算により初期値-1を保持し、以降、次のdpを求める場合にも、利用する値が-1であるか否かを判別し、不要な演算を低減することができる
    問題を解くのは簡単だが,実は少し苦労した.何を捕まえて3時間😤 そしてこれは一昨日解決した問題で、今から発表します.ああ、最近つまらないですね.実は私も大体いくつかの文章を書きましたが、私は確かに問題を解く方法をマスターしました.もしあなたがこの文章を読んだら、知らない人は伝言を残してください.
    コード#コード#
    import java.io.*;
import java.util.*;

public class Main {
    static int[][] distance;
    static Point[] points;
    public static class Point{
        private int x;
        private int y;
        Point(int x, int y){
            this.x = x;
            this.y = y;
        }
    }

    public static int calculateDistance(int a, int b){
        if(distance[a][b] == -1) {
            int dis = Math.abs(points[a].x-points[b].x) + Math.abs(points[a].y-points[b].y);
            distance[a][b] = dis;
            distance[b][a] = dis;
        }
        return distance[a][b];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // reader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); // writer
        StringTokenizer st; // tokenizer

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        points = new Point[n];
        int[][] dp = new int[k+1][n];
        distance = new int[n][n];

        int[] arr;
        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            points[i] = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));

            arr = new int[n];
            Arrays.fill(arr, -1);
            distance[i] = arr;
        }

        for(int i=0; i<=k; i++) {
            arr = new int[n];
            Arrays.fill(arr, -1);
            dp[i] = arr;
            if(i==0) dp[i][0] = 0;
        }

        int min, temp;
        for(int i=1; i<n; i++){
            for(int j=0; j<=k; j++){
                if(i-j > 0){
                    min = Integer.MAX_VALUE;
                    for(int z=0; z<=j; z++){
                        temp = dp[j-z][i-z-1];
                        if(temp == -1) continue;
                        min = Math.min(min, temp+calculateDistance(i-z-1, i));
                    }
                    dp[j][i] = min;
                }
            }
        }

        int result = dp[0][n-1];
        for(int i=1; i<=k; i++){
            if(dp[i][n-1] < result) result = dp[i][n-1];
        }
        bw.write(String.valueOf(result));

        bw.write( "\n"); // for return value
        bw.flush(); // flush
        bw.close(); // close
        br.close(); // close
    }
}
    メタバース(少なくともOculus Questブラウザーのための)のための2 Dウェブサイトを構築すること
    でCのPDFファイルを作成する方法