11722
1115 ワード
質問する
数列Aが与えられると、最長の減少部分数列を求めるプログラムが作成される.
例えば、A={10,30,10,20,20,10}を数えると、最も減衰が長い部分はA={10,30,10,20,20,10}となり、長さは3となる.
入力
第1行は、数列AのサイズN(1≦N≦1000)を与える.
2行目は、数列Aを構成するAiを与える.(1 ≤ Ai ≤ 1,000)
しゅつりょく
第1行出力数列Aの最長減少部分数列の長さ.
に答える
解答は、最も長く増加した部分数列(11053)の問題と同じです.
コード#コード#
#include <iostream>
using namespace std;
int check_max(int* arr, int size)
{
int max = arr[1];
for (int i = 2; i <= size; i++)
{
if (max < arr[i])
max = arr[i];
}
return (max);
}
int main()
{
int n;
int arr[1010];
int DP[10010];
cin >> n;
for (int i = 1; i <= n; i++)
cin >> arr[i];
for (int i = 1; i <= n; i++)
DP[i] = 1;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= i; j++)
{
if (arr[i] < arr[j])
if (DP[i] <= DP[j])
DP[i] = DP[j] + 1;
}
}
printf("%d", check_max(DP, n));
}
Reference
この問題について(11722), 我々は、より多くの情報をここで見つけました
https://velog.io/@lsmmay322/백준-11722
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
第1行は、数列AのサイズN(1≦N≦1000)を与える.
2行目は、数列Aを構成するAiを与える.(1 ≤ Ai ≤ 1,000)
しゅつりょく
第1行出力数列Aの最長減少部分数列の長さ.
に答える
解答は、最も長く増加した部分数列(11053)の問題と同じです.
コード#コード#
#include <iostream>
using namespace std;
int check_max(int* arr, int size)
{
int max = arr[1];
for (int i = 2; i <= size; i++)
{
if (max < arr[i])
max = arr[i];
}
return (max);
}
int main()
{
int n;
int arr[1010];
int DP[10010];
cin >> n;
for (int i = 1; i <= n; i++)
cin >> arr[i];
for (int i = 1; i <= n; i++)
DP[i] = 1;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= i; j++)
{
if (arr[i] < arr[j])
if (DP[i] <= DP[j])
DP[i] = DP[j] + 1;
}
}
printf("%d", check_max(DP, n));
}
Reference
この問題について(11722), 我々は、より多くの情報をここで見つけました
https://velog.io/@lsmmay322/백준-11722
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
解答は、最も長く増加した部分数列(11053)の問題と同じです.
コード#コード#
#include <iostream>
using namespace std;
int check_max(int* arr, int size)
{
int max = arr[1];
for (int i = 2; i <= size; i++)
{
if (max < arr[i])
max = arr[i];
}
return (max);
}
int main()
{
int n;
int arr[1010];
int DP[10010];
cin >> n;
for (int i = 1; i <= n; i++)
cin >> arr[i];
for (int i = 1; i <= n; i++)
DP[i] = 1;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= i; j++)
{
if (arr[i] < arr[j])
if (DP[i] <= DP[j])
DP[i] = DP[j] + 1;
}
}
printf("%d", check_max(DP, n));
}
Reference
この問題について(11722), 我々は、より多くの情報をここで見つけました https://velog.io/@lsmmay322/백준-11722テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol