[C++]伯俊#11054:最も長い生物特徴部分数列

2101 ワード
白駿 ps DP テキストリンク
問題の説明

解法
特徴は減少や増加の部分を探すことではありません.
「必須」は成長の中で成長を終了します.
これは再減少部分の最大長を探す問題である.
しかも数列の長さが1000以下なので、O(n^2)で解いても大丈夫です.
全体的なアルゴリズムは次のとおりです.
  • 増分部の長さは、DP 1[]に記憶される.
  • 削減部の長さは、DP 2[]に記憶される.
  • の増加は終了し、減少の開始部分は同じになります.したがって,上の2つのDP配列を迂回して,対応する部分の和が最大の点を探す.
    • 重要なのは、DPアレイに必要な値を格納する方法です.
    dp maxはインクリメンタル配列を格納するために使用される.
    ストレージ削減部の配列をdp minと宣言します.
    dp maxは入力配列(arr)を二重ポインタ(?)とする感覚で2重探索を行う.探索中にarr[j]dp_max[i] = max(dp_max[i], dp_max[j] + 1)
    を選択して保存します.
    プローブは重複する繰り返し文で行われるため、dp max[i]はarr[0]からarr[i]までの増分部分の最長値となる.
    減少した部分も同様に行われる.
    しかし、dpはarrに対して行われ、dp minはdp maxをコピーして使用する必要がある.
    増加と減少が連続して行われるからだ.
    arr[j]>arr[i]の位置
    dp_min[i] = max(dp_min[i], dp_min[j] + 1);
    実行すると、dp min[i]とarr[j]が減少した部分に含まれ、プラス1の値より大きい値がdp min[i]に格納される.すなわち、iの最初の要素に格納される最長のバイナリ部分数列の長さである.
    手に入れたのにずっと間違いがあった
    答えはdp min[n]ではなく,dp minの要素の中で最大の値である.
    それも容易ではない問題だが、自分で解決したのは少し嬉しい.
    十分に解決できる.acスタンダードボール3!
    ソースコード
    #include <bits/stdc++.h>
using namespace std;

// 1 5 2 1 4 3 4 5 2 1
// 1 2 2 2 3 3 4 5 2 1
// 1 2 3 4 3 4 4 5 6 7 

int arr[1010];
int dp_max[1010];
int dp_min[1010];

int main() {
	ios::sync_with_stdio(false);
	
	int n;

	cin >> n;

	for (int i = 0; i < n; i++)
		dp_max[i] = 1;

	for (int i = 0; i < n; i++)
		cin >> arr[i];

	for (int i = 1; i < n; i++)
	{
		int temp_min = arr[0];

		for (int j = 0; j < i; j++)
		{
			if (arr[j] < arr[i])
			{
				temp_min = arr[j];
				dp_max[i] = max(dp_max[i], dp_max[j] + 1);
				continue;
			}
		}
	}

	for (int i = 0; i < n; i++)
		dp_min[i] = dp_max[i];

	for (int i = 1; i < n; i++)
	{
		int temp_max = arr[0];

		for (int j = 0; j < i; j++)
		{
			if (arr[j] > arr[i])
			{
				temp_max = arr[j];
				dp_min[i] = max(dp_min[i], dp_min[j] + 1);
			}
		}
	}

	int ans = dp_min[0];

	for (int i = 1; i < n; i++)
	{
		if (ans < dp_min[i])
			ans = dp_min[i];
	}

	cout << ans;

	return 0;
}
    [プログラマーレベル1]整数平方根判別問題を解く
    [白俊]1261:アルゴ駅(JAVA)