最長上昇サブシーケンスの2つのアルゴリズム
1509 ワード
最長上昇サブシーケンス英文フルネーム:Longest Increasing Subsequence
一.O(n*n)アルゴリズム,dp[i]はaiを末尾とする最長上昇サブシーケンスの長さを表すが,aiを末尾とする最長上昇サブシーケンスは2つある.aiのみを含むサブシーケンス; 2.jを満たす
次のような関係があります.
dp[i]=max{1,dp[j]+1|j
コード:
二.O(nlogn)アルゴリズム,dp[i]=長さi+1の立ち上がりサブシーケンスにおける末尾要素の最小値(存在しなければINF)
このアルゴリズムでは、STLのlower_bound()関数は便利です.
コード:
もう1つのコードがあります.
この2つのコードはHDU 1257直接ACコードである.
一.O(n*n)アルゴリズム,dp[i]はaiを末尾とする最長上昇サブシーケンスの長さを表すが,aiを末尾とする最長上昇サブシーケンスは2つある.aiのみを含むサブシーケンス; 2.jを満たす
次のような関係があります.
dp[i]=max{1,dp[j]+1|j
コード:
#include
#include
#include
using namespace std;
int a[10010];
int dp[10010];
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
for(int i=0;i
二.O(nlogn)アルゴリズム,dp[i]=長さi+1の立ち上がりサブシーケンスにおける末尾要素の最小値(存在しなければINF)
このアルゴリズムでは、STLのlower_bound()関数は便利です.
コード:
#include
#include
#include
using namespace std;
#define INF 0x3f3f3f
int dp[10010];//dp[i] i+1 ;
int a[10010];
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
for(int i=0;i=a[i] , a[i] ;
}
printf("%d
",lower_bound(dp,dp+n,INF)-dp);// INF ;
}
return 0;
}
もう1つのコードがあります.
for(int i=1;i<=n;i++)
{
int k=lower_bound(g+1,g+n+1,a[i])-g;// a[i] ,
//K a[i] , g 1 +1;
dp[i]=k;
g[k]=min(g[k],a[i]);// , ;
ans=max(dp[i],ans);// ;
}
この2つのコードはHDU 1257直接ACコードである.