DP——線形dpのLIS

3770 ワード
ダイナミック？プログラム
POJ 1631
LIS解析:
LISはlongest Increasing Sequenceが典型的な線形DP問題であり、n^2のアルゴリズムを求めることができる2つのアルゴリズムがあり、a:1-nのシーケンスfor i 1->n for j 1->i dp[i]=1 d[i]=max{dp[i],dp[j]+1(a[j]もう1つのnlogn(ステルスDP)は、a:1-nのシーケンスをb記録長iサブシーケンスの最小末尾数のシーケンス//サブシーケンス単調for i 1->n k++またはbinaryとする.
AC code: 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 4e4 + 100;

int a[maxn];
int b[maxn];


int binary(int st, int ed,int x)
{
    int mid;
    while(ed - st > 1)
    {
        mid = st + (ed-st)/2;
        if(b[mid] == x)  return mid;
        if(b[mid] < x)   st = mid;
        else             ed = mid;
    }
    return ed;
}
int LIS(int p)
{
   int k = 1;
   memset(b,0,sizeof(0));
   b[1] = a[0];
   for(int i = 1; i < p; i++)
   {
      int x = a[i];
      if(x > b[k])  b[++k] = x;
      else if(x < b[1]) b[1] = x;
      else
      {
      int j = binary(1,k,x);
      b[j] = min(b[j],x);
      }
   }
   return k;
}

int main()
{
    int n,p;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d",&p);
        for(int i = 0; i < p; i++)
        {
            scanf("%d",&a[i]);
        }
        int ans = LIS(p);
        printf("%d
",ans);
    }
    return 0;
}
整列配列における数値の出現回数
せんけいふるいほうそすう