[伯俊11054]最長のVitonic部分数列

10982 ワード
適用 DP LIS テキストリンク
https://www.acmicpc.net/problem/11054
質問する
数列SはいくつのSkをベースにして、S 1 Sk+1 > ... SN−1>SNが満足すれば,その数列を頼むニック数列と呼ぶ.
例えば、{10、20、30、25、20}および{10、20、30、40}、{50、40、25、10}はバイナリ数列であり、{1、2、3、2、1}および{10、20、30、40、20、30}はバイナリ数列ではない.
数列Aが与えられた場合、その数列の2進数列および最長数列の長さを計算するプログラムを作成します.
入力
1行目には数列Aの大きさNが与えられ、2行目には数列AのAiが与えられる.(1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)
しゅつりょく
第1行出力数列Aの部分数列のうち最も長い2進数列の長さ
アイデア
LIS、LDSについては、各要素を始点/終点時の長さとして記録する
しかし、LISは後ろのLISを参照して、これらの要素が前に貼ることができるかどうかをチェックして求めます.
しかし、各LDSは前のLDSを参照し、これらの要素が末尾に付加できるかどうかをチェックして求める.
最後に、各要素のLIS+LDS-1は最も長い2進数列長である.
コード#コード#
#include<iostream>
#include<algorithm>
using namespace std;
//lis lds 같이
int main() {
	int n;
	cin >> n;
	int *a = new int[n];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}

	int *b = new int[n];

	b[0] = 1;
    //lds구함
	for (int i = 0; i <= n - 1; i++) {
		b[i] = 1;
		for (int j = 0; j < i; j++) {
			if (a[j] < a[i]) {
				b[i] = max(b[i], b[j] + 1);
			}
			
		}
	}


	//뒤에서부터 작은 LiS 계산(나로부터 시작하는)
	int *c = new int[n];


	c[n - 1] = 1;


	for (int i = n - 1; i >= 0; i--) {
		int diff = n - 1 - i;//i== n-2면 diff==1

		c[i] = 1;//나 자신이 b[i]인 경우
		
		for (int j = 1; j <= diff; j++) {
			//b[i+j]중 나랑 매치되는 것 중 가장 큰 것 찾기
			//만약 못찾는다면 나 자신이 b[i]가 된다
			if (a[i + j] < a[i]) {
				c[i] = max(c[i], c[i + j] + 1);
			}
		}
	}
	int res = 0;
	
	for (int i = 0; i < n; i++) {
		res = max(res, b[i] + c[i]-1);
	}

	cout << res << endl;

	/*
	for (int i = n - 1; i >= 0; i--) {
		cout << "i는 \t" << i << "\t" << b[i] << "\t"<<c[i]<< endl;
		
	}
	*/
	
	//b[0]가 답이 아니다!!!!
	delete[] a;
	delete[] b;
	delete[] c;
}
Redisオブジェクトインスタンスの小さな例
asp.Net判断ブラウザバージョンコード