C++動的計画アルゴリズムの最長上昇サブシーケンス
1266 ワード
最長上昇サブシーケンス
Description
b 1Input
入力される最初の行は、シーケンスの長さN(1<=N<=1000)である.2行目には、シーケンス内のN個の整数が与えられ、これらの整数の値範囲はいずれも0〜10000である.
Output
最長上昇サブシーケンスの長さ.
Sample Input
Sample Output
この問題はダイナミックプランニングの入門の重要な例題であり、ダイナミックプランニングの第一歩であり、非常に重要である.
コードは次のとおりです.
最長上昇サブシーケンス
Description
b 1Input
入力される最初の行は、シーケンスの長さN(1<=N<=1000)である.2行目には、シーケンス内のN個の整数が与えられ、これらの整数の値範囲はいずれも0〜10000である.
Output
最長上昇サブシーケンスの長さ.
Sample Input
7
1 7 3 5 9 4 8Sample Output
4この問題はダイナミックプランニングの入門の重要な例題であり、ダイナミックプランニングの第一歩であり、非常に重要である.
コードは次のとおりです.
#include<cstdio>
#include<cstring>
int num[4][1001],n;
main()
{
memset(num[2],1,sizeof(num[2]));
memset(num[3],0,sizeof(num[3]));
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&num[1][i]);
for(int i=n-1;i>0;i--)
{
int x=0,y=0;
for(int j=i+1;j<=n;j++)
if(num[1][i]<num[1][j]&&num[2][j]>x)
{
x=num[2][j];
y=j;
}
if(x){num[2][i]=x+1;num[3][i]=y;}
}
int t=0,sum=0;
for(int i=1;i<=n;i++)
if(num[2][i]>=num[2][t])t=i;
while(t)
{
t=num[3][t];
sum++;
}
printf("%d
",sum);
}