[規格11053]最長成長部分数列(C++)

1778 ワード
DP 白駿 ps テキストリンク
BOJショートカット 
#include <iostream>
using namespace std;
int go(int);
int d[1001] = { 0 };
int arr[1001] = { 0 };
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n; cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> arr[i];
	int max = 1; // 길이는 1 이상
	for (int i = 1; i <= n; i++) {
		if (i == 1)
			max = go(i);
		else
			if (go(i) > max)
				max = go(i);
	}
	cout << max;
	return 0;
}
int go(int n) {
	d[1] = 1;
	if (d[n])
		return d[n];
	for (int i = 1; i < n; i++) {
		if (arr[i] < arr[n])
			d[n] = max(d[n], d[i] + 1);
	}
	if (d[n] == 0) // arr[n]이 배열에서 가장 작은 수일 경우
		d[n] = 1;
	return d[n];
}
問題を誤って理解し,長いこと解いてやっとはっきりした.
A={10,20,10,30,30,20,50}を数えると,最も長く成長する数は{10,20,30,50}である.数列Aで生成できる増分数列には、{10,20,{10,20,50}などがあり、その中で「最長」数列を見つけてその長さを求める.
私はTOP-DOWNでこの問題を解決しました.
d[n]は、長さnの数列の中で最も長い数列の長さを表す.
int go(int n) {
	d[1] = 1;
	if (d[n])
		return d[n];
	for (int i = 1; i < n; i++) {
		if (arr[i] < arr[n])
			d[n] = max(d[n], d[i] + 1);
	}
	if (d[n] == 0) // arr[n]이 배열에서 가장 작은 수일 경우
		d[n] = 1;
	return d[n];
}
0に初期化された配列dがある.arr[n]より小さく最大のarr[i]を求め、d[n]にd[i]+1の値を加算する.
この時は少し注意が必要です.arr[n]より小さく、最大のarr[i]がない場合、すなわちarr[n]が最小の数字である場合、d[n]は1であるべきである.私はこの部分を逃して、いつも間違いばかりだったので、しばらくうろうろしました.次のコードが漏れないように注意してください.
if (d[n] == 0) // arr[n]이 배열에서 가장 작은 수일 경우
		d[n] = 1;
main関数では、go(1)、go(2)、...、go(n)の最大値を変数maxに割り当てて出力します.
Pandasとdashを使用したコロナサイトの作成-環境の設定、データのマージ
[白俊]15684号梯子操作(C++,三星機出)