[規格14002]最長成長部分数列4(C++)
BOJショートカット
▼私のソースコード
これは上の問題とあまり差がない.違いがある場合は、数列のすべての数を出力する必要があります.実装方法を考慮すると,d[n]に対応する数列を格納する方法で問題を解決する2次元配列が作成された.その後、白俊のアルゴリズムの授業を聞いて、「逆追跡」で実現しやすくなった.
▼ソースコードを参照
▼私のソースコード
#include <iostream>
using namespace std;
int go(int);
int d[1001] = { 0 }, dnum[1001][1001] = { 0 }, 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 이상
int p = 0;
for (int i = 1; i <= n; i++) {
if (i == 1) {
max = go(i);
p = i;
}
else
if (go(i) > max) {
max = go(i);
p = i;
}
}
cout << max <<'\n';
for (int i = 1; dnum[p][i] != 0; i++) {
cout << dnum[p][i] << ' ';
}
return 0;
}
int go(int n) {
d[1] = 1; dnum[1][1] = arr[1];
if (d[n])
return d[n];
int k;
// d[n]을 가능한 한 최댓값으로 갱신
for (int i = 1; i < n; i++) {
if (arr[i] < arr[n]) {
if (d[n] < d[i] + 1) {
d[n] = max(d[n], d[i] + 1);
k = i;
}
}
}
// dnum 배열에 값 넣어주기
if (d[n] != 0) {
for (int i = 1; i <= n-1; i++) {
dnum[n][i] = dnum[k][i]; // 새로운 배열에 가장 긴 배열 복붙
}
for (int i = 1; i <= n ; i++) { // 배열의 마지막에 arr[n] 추가
if (dnum[n][i] == 0) {
dnum[n][i] = arr[n];
break;
}
}
}
else { // arr[n]이 배열에서 가장 작은 수일 경우
d[n] = 1;
dnum[n][1] = arr[n];
}
return d[n];
}
[規格11053]最長成長部分数列(C++) これは上の問題とあまり差がない.違いがある場合は、数列のすべての数を出力する必要があります.実装方法を考慮すると,d[n]に対応する数列を格納する方法で問題を解決する2次元配列が作成された.その後、白俊のアルゴリズムの授業を聞いて、「逆追跡」で実現しやすくなった.
▼ソースコードを参照
void go(int p) {
// ? -> ? -> ... a[v[p]] -> a[p]
// ---------------------
// go(v[p]);
if (p == -1) {
return ;
}
go(v[p]);
cout << a[p] << ' ';
}
v[p]はa[p]に接続された装置である.関数内で関数を再呼び出すことで、数列内の数字が順次出力されます.このアルゴリズムを覚えたほうがいい.Reference
この問題について([規格14002]最長成長部分数列4(C++)), 我々は、より多くの情報をここで見つけました https://velog.io/@yoohoo030/백준14002-가장-긴-증가하는-부분-수열-4-Cテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol