プログラマ専用SNS ミクプラ

問題

現在カザフスタンがある地域には，古くは「シルクロード」と呼ばれる交易路があった．

シルクロード上には N + 1 個の都市があり，西から順に都市 0, 都市 1, ... , 都市 N と番号がつけられている．都市 i - 1 と都市 i の間の距離 (1 ≦ i ≦ N) は Di である．

貿易商である JOI 君は，都市 0 から出発して，都市を順番に経由し，都市 N まで絹を運ぶことになった．都市 0 から都市 N まで M 日以内に移動しなければならない．JOI 君は，それぞれの日の行動として，以下の 2 つのうちいずれか 1 つを選ぶ．

移動：現在の都市から 1 つ東の都市へ 1 日かけて移動する．現在都市 i - 1 (1 ≦ i ≦ N) にいる場合は，都市 i に移動する．
待機：移動を行わず，現在いる都市で 1 日待機する．
移動は大変であり，移動するたびに疲労度が溜まっていく．シルクロードでは日毎に天候の変動があり，天候が悪い日ほど移動には苦労を要する．

JOI 君が絹を運ぶのに使える M 日間のうち j 日目 (1 ≦ j ≦ M) の天候の悪さは Cj であることが分かっている．都市 i - 1 から都市 i (1 ≦ i ≦ N) に j 日目 (1 ≦ j ≦ M) に移動する場合，疲労度が Di × Cj だけ溜まってしまう．移動を行わず待機している日は疲労度は溜まらない．

JOI 君は，それぞれの日の行動をうまく選ぶことで，できるだけ疲労度を溜めずに移動したい．JOI 君が M 日以内に都市 N に移動するときの，移動を開始してから終了するまでに溜まる疲労度の合計の最小値を求めよ．

入力

入力は 1 + N + M 行からなる．

1 行目には，2 つの整数 N, M (1 ≦ N ≦ M ≦ 1000) が空白を区切りとして書かれている．これは，シルクロードが N + 1 個の都市からなり，JOI 君が絹を都市 0 から都市 N まで M 日以内に運ばなければならないことを表す．

続く N 行のうちの i 行目 (1 ≦ i ≦ N) には，整数 Di (1 ≦ Di ≦ 1000) が書かれている．これは，都市 i - 1 と都市 i の間の距離が Di であることを表す．

続く M 行のうちの j 行目 (1 ≦ j ≦ M) には，整数 Cj (1 ≦ Cj ≦ 1000) が書かれている．これは，j 日目の天候の悪さが Cj であることを表す．

出力

JOI 君が M 日以内に都市 N に移動するときの，移動を開始してから終了するまでに溜まる疲労度の合計の最小値を 1 行で出力せよ．

サンプルコード

コード:

#include <cstdio>
#include <cstring>

void chmin(int& t, int f) { if (f < t) t = f; }
int in() { int x; scanf("%d", &x); return x; }

int D[1024], C[1024], dp[1024][1024];

int main() {
  int N = in();
  int M = in();

  for (int i = 0; i < N; ++i) {
    D[i] = in();
  }
  for (int j = 0; j < M; ++j) {
    C[j] = in();
  }

  memset(dp, 0x3f, sizeof(dp));
  dp[0][0] = 0;
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < M; ++j) {
      chmin(dp[i][j + 1], dp[i][j]);
      chmin(dp[i + 1][j + 1], dp[i][j] + D[i] * C[j]);
    }
  }

  int res = 1001001001;
  for (int j = 1; j <= M; ++j) {
    chmin(res, dp[N][j]);
  }
  printf("%d\n", res);

  return 0;
}

去年のJOI予選第4問です。
サンプルコードの、入力されたDとCの値を配列に代入し終えたあとの処理(20行目以降)が解説を読んでも理解できません。
詳しくお願いします。

公式の解説ページ

具体的なデータで試してみればすぐにわかりますよ。

入力

コード:

return 0; の前に次のコードを入れて、dp の値を見てみましょう。

コード:

  for (int i = 0; i <= N; ++i) {
    for (int j = 0; j < M; ++j) {
      printf("%12d", dp[i][j]);
    }
	printf("\n");
  }

出力

コード:

120
           0           0           0           0           0           0
  1061109567          10          10          10          10          10
  1061109567  1061109567         160         100          40          40
  1061109567  1061109567  1061109567         220         120         160

1061109567 は 0x3f3f3f3f で、memset(dp, 0x3f, sizeof(dp));でセットされた値。
次に、この表を初期状態(全部 1061109567 で、dp[0][0] だけ 0)から、
プログラムに従って自分で書き込んでいってみてください。
都市 i に、j 日めまでに着く最小の疲労度の表になるのが分かるでしょう。

かずまさんが書きました:return 0; の前に次のコードを入れて、dp の値を見てみましょう

すみません。j の値が 1つ少なかったので、次のように訂正。

コード:

  for (int i = 0; i <= N; ++i) {
    for (int j = 0; j <= M; ++j) {
      printf("%11d", dp[i][j]);
    }
	printf("\n");
  }

出力

コード:

120
          0          0          0          0          0          0          0
 1061109567         10         10         10         10         10         10
 1061109567 1061109567        160        100         40         40         40
 1061109567 1061109567 1061109567        220        120        160        200

かずまさんが書きました: 1061109567 は 0x3f3f3f3f で、memset(dp, 0x3f, sizeof(dp));でセットされた値。
次に、この表を初期状態(全部 1061109567 で、dp[0][0] だけ 0)から、
プログラムに従って自分で書き込んでいってみてください。

この初期状態にセットされた値(1061109567)にはどのような意味があるのでしょうか？

なんとなく自己解決できたような気がします。
このような解釈でいいんでしょうか？

コード:


#include <iostream>
#include <algorithm>

using namespace std;

int search(int i, int j);

static int D[1005], C[1005];
static int dp[1005][1005];
int main() {

	int M, N;
	cin >> N >> M;
	
	for (int i = 0; i < N; i++) {
		int d = 0;
		cin >> d;
		D[i] = d;
	}
	for (int j = 0; j < M; j++) {
		int c = 0;
		cin >> c;
		C[j] = c;
	}
	/*
	for (int i = 0; i < N; i++) {
		cout << "D[" << i << "]=" << D[i] << "\n";
	}
	for (int j = 0; j < M; j++) {
		cout << "C[" << j << "]=" << C[j] << "\n"; 
	}
	*/

	memset(dp, 0x3F, sizeof(dp));
	dp[0][0] = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			dp[i][j + 1] = min(dp[i][j], dp[i][j + 1]);
			dp[i + 1][j + 1] = dp[i][j] + D[i] * C[j];
			//最初に前回行動した場合の疲労度を入れておき、iが次のループに入ったときに前回待機した場合の疲労度と比較
		}
	}
	/*
	for (int i = 0; i <= N; ++i) {
		for (int j = 0; j <= M; ++j) {
			printf("%11d", dp[i][j]);
		}
		printf("\n");
	}
	*/

	int result = 1061109567; // =0x3F(HEX)
	for (int j = 1;j <= M;j++) {
		result = min(result, dp[N][j]);
	}
	cout << result;

	return 0;
}

0x3Fについては、このページが参考になりました。

プログラマ専用SNS ミクプラ

以下のコードの解説をお願いします。

以下のコードの解説をお願いします。

Re: 以下のコードの解説をお願いします。

Re: 以下のコードの解説をお願いします。

Re: 以下のコードの解説をお願いします。

Re: 以下のコードの解説をお願いします。