[線形ダイナミックプランニング][最長上昇/下降シーケンス][P 1020ミサイル迎撃]線形ダイナミックプランニング問題の理解と総括

原題リンク:ミサイル迎撃
タイトルの説明
ある国は敵国のミサイル攻撃を防ぐために、ミサイル迎撃システムを発展させた.しかし、このミサイル迎撃システムには欠陥がある.最初の砲弾は任意の高さに達することができるが、その後、各砲弾は前の砲弾の高さを上回ることができない.ある日、レーダーは敵国のミサイル襲撃を捉えた.このシステムはまだ試用段階にあるため、1つのシステムしかないため、すべてのミサイルを遮断できない可能性がある.
ミサイルが順次飛来する高さ(レーダーが与えた高さデータは≦50000の正の整数)を入力し、このシステムが最大でどれだけのミサイルを遮断できるかを計算し、すべてのミサイルを遮断するには少なくともどれだけのミサイル遮断システムを配備しなければならないかを計算する.
にゅうしゅつりょくけいしき
入力形式:
1行、数個の整数(個数≦100000)
出力フォーマット:
2行、1行ごとに1つの整数で、最初の数字はこのシステムが最大でどれだけのミサイルを遮断できるかを示し、2番目の数字はすべてのミサイルを遮断するには少なくともどれだけのミサイル遮断システムを配備するかを示しています.
O(N^2)メソッド:
問題の意味から分かるように,第1の問題は最長上昇サブシーケンスを問い,第2の問いは最長上昇サブシーケンス(Dilworth定理)を求める.
ダイナミックプランニングの考え方を利用して、2つのサイクルでシーケンスの長さを求めればいい.

#include 
#include 
#include 

using namespace std;

int Height[100001];
int DP[100001];
int DP2[100001];

int main(void)
{
    int Tmp;
    int Index = 1;
    int ans1 = 0;
    int ans2 = 0;
    
    while(scanf("%d",&Tmp) != EOF)
    {
        Height[Index] = Tmp;
        Index++;
    }
    
    for(int i = Index;i > 0;i--)
    {
        for(int j = 1;j <= Index;j++)
        {
            if(i < j && Height[i] >= Height[j])
            {
                DP[i] = max(DP[i],DP[j]+1);
            }
        }
        ans1 = max(ans1,DP[i]);
    }
    
    for(int i = 1;i < Index;i++)
    {
        DP2[i] = 1;
        
        for(int j = 1;j < i;j++)
        {
            if(Height[j] < Height[i])
            {
                DP2[i] = max(DP2[i],DP2[j]+1);
            }
        }
        ans2 = max(ans2,DP2[i]);
    }
    cout << ans1 << endl;
    cout << ans2 << endl; 
    return 0;
}

O(nlogn)の方法:
(木の配列コードは短くて精悍で、その基本的な使い方は1つの配列のある区間の和を求めて、アクセスと修正の時間の複雑度はO(nlogn)です)
ツリー配列学習記事
樹状配列の手法を用いて,ミサイル高さを樹状配列として下標にアクセスし,逆順遍歴と正順遍歴の手法により最長配列を求める.
自分で手動でシミュレーションして理解を深めることができます.

#include 
#include 

using namespace std;

int Add(int,int);
int Query(int);
int lowbit(int);

int TreeDp[50001];
int Height[100001];
int N;
int MaxN;

int main(void)
{
    memset(TreeDp,0,sizeof(TreeDp));
    int ans1 = 0,ans2 = 0;
    int index = 1;
    while(cin >> Height[index])
    {
        MaxN = max(MaxN,Height[index]);
        index++;
    }
    index--;
    //       ，          
    for(int i = index;i > 0;i--)
    {
        //       
        int MaxAns = Query(Height[i])+1;
        Add(Height[i],MaxAns);
        ans1 = max(ans1,MaxAns);
    }
    memset(TreeDp,0,sizeof(TreeDp));
    
    //             DP        ，  ，        
    for(int i= 1;i<=index;i++)
    {
        //                        ，             
        int MaxAns = Query(Height[i]-1)+1;
        Add(Height[i],MaxAns);
        ans2 = max(ans2,MaxAns);
    }
    cout << ans1 << "
" << ans2 << endl;
    return 0;
}

int lowbit(int i)
{
    return (-i)&i;
}

int Add(int x,int y)
{
    for(int i = x;i <= MaxN;i+=lowbit(i))
    {
        TreeDp[i] = max(TreeDp[i],y);
    }
    return 0;
}

int Query(int x)
{
    int ans = 0;
    for(int i = x;i > 0;i-=lowbit(i))
    {
        ans = max(TreeDp[i],ans);
    }
    return ans;
}