白駿11053.最長のローカル数列−問題解(c++)(dp)

2111 ワード
どうてきけいかくほう 白駿 DP boj テキストリンク

🔎 11053.問題を見る


https://www.acmicpc.net/problem/11053

💡 問題を解く前に


📝 コードの表示

#include <bits/stdc++.h>
using namespace std;

int n;
int a[1111111];
int cache[1111111];

int solve(int start) {
	int &ret=cache[start+1];
	if(ret!=-1) return ret;
	
	ret=0;  // *중요*
	for(int i=start+1; i<n; i++) {
		if(start==-1 || a[start]<a[i]) {
			ret = max(ret, solve(i)+1);
		}
	}
	
	return ret;
}

int main() {
	cin >> n;
	for(int i=0; i<n; i++) {
		cin >> a[i];
	}
	
	memset(cache, -1, sizeof(cache));
	cout << solve(-1) << "\n";
	
	for(int i=0; i<=n; i++) {
		cout << cache[i] <<  " ";
	}
	return 0;
}

🎈 コード解釈と関連概念


時間複雑度O(n^2)


例えば、4つの数字がある場合、
-1からstartが3になるまで,解(i)を繰り返す.
各解(i)はiex) solve(-1): solve(-1) -> solve(0) -> solve(1) -> solve(2) -> solve(3)
ここで、solve(0)は、solve(0)が1回で終わるのではなく、for文solve(0)->solve(1)->solve(2)->solve(3)iがnの前にも実行される.
84日目:午後9時のソフトコード
jsonデータを構造体に変換