2021-01-31

ミサイル防御システム【dfs】
今日はシロACM合宿の日で、それからデータの构造は本当に难しくて、本当に学ぶことができなくて、それから助けることができなくて以前の问题を复习して、以前SDUT程设の2の中で1つの问题が最低ブロックシステムということを覚えていて、それは1つの贪欲で、私个人は最も长い上升のサブシーケンスの考えはそれと少し似ていると思います.まずこの問題を分析して、この最小遮断システムの問題幹とコードを導入します:最小遮断システムDescriptionは問題幹を精錬して、いくつかのミサイルが飛んできて、砲弾システムで順番に遮断する必要があります.その最初の砲弾は任意の高さに達することができますが、その後、砲弾ごとに前の砲弾の高さを超えることはできません.例えば、これまでのすべてのミサイルよりも高いミサイルが飛んできたら、遮断システムを増やすしかありません.ブロックシステムの個数を求めるInput入力は、ミサイルの総個数(正の整数)、ミサイルが飛来する高さ(レーダーが与える高さデータは30000以下の正の整数で、スペースで区切られている)を含む.
Outputは出力迎撃に対応するすべてのミサイルに対して少なくとも何セットのこのようなミサイル迎撃システムを配備しなければならない.
Sample Input 8 389 207 155 300 299 170 158 65 Output 2

#include 
#include 
int a,i;//          
int b[100000];//                
int main()
{
     
	int n,cnt;//n          ，cnt          
	while(scanf("%d",&n)!=EOF)
	{
     
		memset(b,0,sizeof(b));//b                  
		cnt=1;	
		for(i=0;i<n;i++)
		{
        
			scanf("%d",&a);
			if(i==0)
			  b[0]=a;
			int j;
			for(j=0;j<cnt;j++)//            b     
			{
     
				if(b[j]>=a)//              
				{
     
					b[j]=a;
					break;
				}
			}
			if(j==cnt)//            ，                
			{
     
				b[cnt++]=a;
			}
		}
		printf("%d
",cnt);
	}
	return 0;
}

この問題は既存の遮断システムで探した問題で、各遮断システムはミサイルが飛んでくると遮断できるかどうかを判断し、各遮断システムが遮断できる最大高さを更新するからだ.最後にカウントのcntを出力すればいいのですが、貪欲な戦略のテーマで、難易度はまあまあです.しかし、今日のこの問題は本当に私にこの白さんをくれました.
187.ミサイル防御システム
近隣の悪意ある国の脅威に対抗するため、R国はミサイル防衛システムを更新したと説明した.
防御システムのミサイル遮断高さは、厳格に単調に上昇しているか、厳格に単調に低下している.
例えば、1セットのシステムが高さ3と高さ4の2発のミサイルを相次いで遮断した場合、次のシステムは高さ4より大きいミサイルしか遮断できない.
襲来する一連のミサイルの高さを与えて、少なくとも何セットの防御システムが必要かを求めて、それらをすべて撃墜することができます.
入力フォーマット入力には、複数のテスト・インスタンスが含まれます.
各試験例について、第1行は整数nを含み、来襲ミサイルの数を表す.
2行目は、各ミサイルの高さを表すn個の異なる整数を含む.
試験用例n=0が入力されると、入力が終了し、その用例は処理する必要がないことを示す.
出力フォーマットは、各テスト例について、必要な防御システムの数を表す1行を占める整数を出力する.
データ範囲1≦n≦50入力サンプル:

5
3 5 2 4 1
0 

出力サンプル:

2

サンプル解釈:サンプルを与えるには、少なくとも2つの防御システムが必要です.
1セットの撃墜高さ3,4のミサイル、もう1セットの撃墜高さ5,2,1のミサイル.问题解:この问题はネット上の大物の解析が多くて、私は白としてもあまり深く理解していないので、间违った认识があるかもしれません.ここでは自分の学習過程を1つだけ記録します.まず私たちは問題を見て、ミサイルが上昇しても下がることができることを知っています.だから、前の問題のように、上昇サブシーケンスの問題をいくつか記録することはできません.私が考えたのは列挙して暴捜することです.1つのミサイルの高さは、増加するシーケンスに置くべきか、減少するシーケンスに置くべきか、そしてどの増加または減少シーケンスに置くべきかが核心的に議論される問題である.この問題は時間の複雑さに要求されるので,検索の過程で常に方法を考えて最適化し,適切な場所で枝を切る.検索:

最初の検索はBFSかもしれませんが、幅が優先されています.ネット上にはこの方法を使っている人がいますが、メモリに保存されているいくつかの書き方がよく分かりません.あまり言いません.

の2番目のDFSは、私が採用した方法です.枝を切る過程で確かに書きやすいので、私はこの方法しか考えられません.それから、グローバル最小値を宣言する記録と反復深さ検索の2つの考え方を採用することができます.時間の複雑さはn*2^nなので、私は前者でこのコードを書きます.

シロもあまりできないので、注釈を書くのが面倒かもしれません.コードは以下の通りです.

#include 
using namespace std;
const int N = 100;
int n;
int q[N];//q：       ; 
int up[N],down[N];
int ans;  //         ;

void dfs(int x,int su,int sd)  // x:        ,su:        ,sd:        
{
     
    if(su + sd >= ans) return ; //   ---         ，return
    if(x==n) //     
    {
     
        ans = su + sd;//                  
        return ;
    }

    //   1：            
    int k =0;//k                  
    while(k < su && up[k] >= q[x]) k++;  //         0   ，   <
    int t=up[k]; //            ; 
    up[k] = q[x];//  q[u]     ，   up  ； 
    if(k < su) dfs(x+1,su,sd); //      ---            m
	//  k>=su  q[  ]          
    else dfs(x+1,su+1,sd);// su+1 （      ），     
    up[k] = t; //         
   //  2    ； 
    //   2：            
    k = 0;
    while(k < sd && down[k] <= q[x]) k ++;
    t = down[k];
    down[k] = q[x];
    if(k < sd) dfs(x+1,su,sd);
    else dfs(x+1,su,sd+1);
    down[k] = t;
}
int main()
{
     
    while(cin >> n&& n)
    {
     
        for(int i=0;i<n;i++)
		  cin >> q[i];
        ans=n;
        dfs(0,0,0);
        cout<<ans<<endl;
    }

    return 0;
}

この問題は私にとって難しいと思います.多くのネット上の大物の考えを参考にして、自分の学習過程だけを記録しましょう.初心者が出発するので,どうぞお許しください.