[伯俊]1965号マウントボックス

1516 ワード
白駿 DP ps テキストリンク

[伯俊]1965号机器人


1.質問


六面体の箱が一列に並んでいる.各箱には大きさがあり、前の箱の大きさが後ろの箱の大きさより小さい場合は、前の箱を後ろの箱に入れることができます.たとえば、前から(1、5、2、3、7)の大きさのボックスが5つある場合、1の大きさのボックスを5のボックスに入れてから、7の大きさのボックスに入れることができます.しかし、箱を置く方法はいろいろあります.前の例では、1、2、3、7のサイズのボックスを順に選択すると、合計4つのボックスが1つのボックスに入ります.
ボックスが大きくなると、プログラムを作成し、一度に入れることができる最大ボックス数を出力します.

2.入力


ファイルの最初の行は、ボックスの個数n(1 ≤ n ≤ 1000)を表す.2行目は各箱の大きさを順番に与えます.箱の大きさは1000を超えない自然数です.

3.出力


最初の行に1行入れることができる最大箱数を出力します.

4.解答

  • 最も成長した部分問題と同じです.

    • 5.コード

    #include <iostream>
#include <algorithm>
using namespace std;

int arr[1000];
int d[1000];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int length;
	cin >> length;

	for (int i = 0; i < length; i++){
		cin >> arr[i];
		d[i] = 1;
	}

	d[0] = 1;
	for (int i = 1; i < length; i++){
		for (int j = 0; j < i; j++){
			if (arr[j] < arr[i]) d[i] = max(d[i], d[j] + 1);
		}
	}
    
	int maxValue = d[0];
	for (int i = 0; i < length; i++){
		maxValue = max(maxValue, d[i]);
	}
	cout << maxValue;
}
    iOS標準のmusicアプリのようなプレイヤーを出せるLNPopupControllerの紹介
    JavaScriptの配列(Array)