[C言語]伯準1149:RGB距離

構想

まず問題を理解してください.

ずっと見逃して△前の色と違っていいです.

入力値を使用するには、2 D配列を使用する必要があります.

和を求めるので和を使います.

ダイナミックプランニング法を使用する場合は、保存する配列を作成する必要があります.

でも1番はどう書けばいいか分からない最高価格を探してどうすればいいの?再帰で最後まで、求和値のminを求めればいいのですが、そうすると必ずタイムアウトします.ダイナミックプランを書いていないので...
に質問

前の色と異なる方法

最高価格を求める方法

動的計画法を用いる方法

どのように问题を解くことを知らないですべてあの3つを知りません...
最終的に検索を決定して受け入れます.まだコードの作成が始まっていません.本当に知らなかったからやらなかった

他者コード1

#include <stdio.h>

int arr[3];
int dp[3];
int dp2[3];
int Min(int a, int b)
{
	return a < b ? a : b;
}
void distance_RGB(int N)
{
	int i;
	dp[0] = dp[1] = dp[2] = 0;
	for (i = 1; i <= N; i++)
	{
		scanf("%d %d %d", &arr[0], &arr[1], &arr[2]);
		dp2[0] = dp[0];
		dp2[1] = dp[1];
		dp2[2] = dp[2];
		dp[0] = Min(dp2[1], dp2[2]) + arr[0];
		dp[1] = Min(dp2[0], dp2[2]) + arr[1];
		dp[2] = Min(dp2[0], dp2[1]) + arr[2];
	}
	int min = Min(Min(dp[0], dp[1]), dp[2]);
	printf("%d", min);
}
int main()
{
	int i;
	int N;
	scanf("%d", &N);
	distance_RGB(N);
}

https://evga7.tistory.com/52コードを理解するには、このコードのほうがいいです.
最初は264083でしたが、その後
同じ色を塗ることができないので、2番目から0番目(R)に1,2番目(G,B)配列の小さい値と、以前に計算したdp値を加えることができます.
1つ目は0、2つ目と2つ目は0、1つ目と1つ目を比較し、前のdp値と比較して求めればよい.
最初のdpは、以前に計算された値がないため、264083を格納する.
そして、dp[0]にdp[1]、dp[2]の値より小さい値とR値を加算する.
残りは、dp[0~3]の値のうちの最小値を出力するように計算してもよい.

他者コード2

#include <stdio.h>
#define MAX 1000*1000

int input[1001][4];
int dp[1001][4];

int min(int x, int y) {
	return x < y ? x : y;
}

int main() {
	int N;
	scanf("%d", &N);
	
	// 입력
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= 3; j++)
			scanf("%d", &input[i][j]);
	
	// dp 배열 채우기
	dp[1][1] = input[1][1];
	dp[1][2] = input[1][2];
	dp[1][3] = input[1][3];

	for (int i = 2; i <= N; i++) {
		dp[i][1] = min(dp[i - 1][2], dp[i - 1][3]) + input[i][1];
		dp[i][2] = min(dp[i - 1][1], dp[i - 1][3]) + input[i][2];
		dp[i][3] = min(dp[i - 1][1], dp[i - 1][2]) + input[i][3];
	}

	// 출력
	int min = MAX + 1;
	for (int i = 1; i <= 3; i++)
		if (dp[N][i] < min)
			min = dp[N][i];
	printf("%d", min);
	return 0;
}

https://wisdom-990629.tistory.com/entry/C-%EB%B0%B1%EC%A4%80-1149%EB%B2%88-RGB%EA%B1%B0%EB%A6%AC
最初の家の色を確認するときは、i-1の家を確認します.
i 1 stアルバム->赤塗り(index 1)の手順
i-1集->緑(index 2)または青(index 3)でなければなりません.
したがって、i-1の家を緑と青に塗ったときの最高価格に赤を加えることができます.
=> dp[i][1] = min(dp[i-1][2], dp[i-1][3]) + input[i][1]
つまり、各家庭に赤、緑、青を塗る場合は、これらの要因を考慮し、条件に応じて使用する必要があります.

{}の部分は1号室から選択した色のインデックスです.
(ex.dp[2][1]->1号室2番インデックス(緑)、2号室1番インデックス(赤)
このようにdp配列を充填すると,dp[N][1]~dp[N][3]で最適値を見つけることができる.
本当に難しすぎて、見続けそうになったし、後の問題も一度見たし、この問題を理解しなければ、後に影響します.
ポイントは、グリッドのように、一番小さい値をつかんでから行くと間違います.
また,前の色と異なる選択方法はindex−1の選択である.これは、dpを埋め込むために最高値を指定する論理です.
ここは時間がたくさん変わるかもしれません.