Description

某國為了防御敵國的導彈襲擊，發展出一種導彈攔截系統。
敵國的導彈形成了立體打擊，每個導彈可以抽象成一個三維空間中的點(x; y; z)。攔截系統發射的炮彈也很好地應對了這種情況，每一發炮彈也可以視為一個三維空間中的點。
但是這種導彈攔截系統有一個缺陷：雖然它的第一發炮彈能夠到達三維空間中任意的點，但是以后每一發炮彈到達點的坐標(x; y; z) 的三個坐標值都必須大于前一發炮彈的對應坐標值。
某天，雷達捕捉到敵國的導彈來襲。由于該系統還在試用階段，所以只有一套系統，因此有可能不能攔截所有的導彈。
輸入導彈飛來的坐標，計算這套系統最多能攔截多少導彈，如果要攔截所有導彈最少要配備多少套這種導彈攔截系統。注意: 所有導彈都是同時飛來的。

Input

第一行一個正整數n，表示敵國導彈數目。
接下來n 行，每行三個非負整數xi，yi，zi，表示一個敵國導彈的三維坐標。
數據保證所有的導彈坐標互不相同。

Output

第一行一個整數，表示一套系統最多攔截的導彈數。
第二行一個整數，表示攔截所有導彈最少配備的系統數。

Sample Input

4
0 0 0
1 1 0
1 1 1
2 2 2

Sample Output

3
2

Data Constraint

對于30% 的數據，n <=10
對于100% 的數據，n <= 1000，x; y; z <= 10^6

Solution

• 對于第一問，我們考慮動態規劃。

• 先按 x 坐標將導彈從小到大排一遍序，設 F[i] 表示攔截的最后一個導彈為 i 的最大攔截數。

• 則顯然有： F[i]=Max{F[j]+1}，其中j∈[1,i)，yj<yi，zj<zi

• 難就難在第二問，如何求最小的攔截系統數。貪心？——不行！

• 考慮一個系統在攔截一個導彈 i 后，還能再攔截一個導彈 j ，則點 i 向 j 連一條有向邊。

• 這樣就形成了一個有向無環圖。求有向圖的最小覆蓋即可（即：多少條不相交路徑可以覆蓋全圖）

• 想到拆點，將一個點拆成兩個點：A點（連出點）和B點（連入點），一個點的A連到另一個點的B。

-這樣就有 N 個A點和 N 個B點，形成一個二分圖。

• 用匈牙利算法求出其最大匹配數 k ，則答案即為 n?k 。（因為每多一個匹配就能少一個系統）

Code

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1001; struct data {int x,y,z; }a[N]; int ans; int b[N<<1][N]; int f[N<<1]; bool bz[N<<1]; inline int read() {int X=0,w=1; char ch=0;while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();return X*w; } inline int max(int x,int y) {return x>y?x:y; } inline bool cmp(data x,data y) {return x.x<y.x; } inline bool Hungary(int x) {for(int i=1;i<=b[x][0];i++)if(!bz[b[x][i]]){bz[b[x][i]]=true;if(!f[b[x][i]] || Hungary(f[b[x][i]])){f[b[x][i]]=x;return true;}}return false; } int main() {int n=read();for(int i=1;i<=n;i++) a[i].x=read(),a[i].y=read(),a[i].z=read();sort(a+1,a+1+n,cmp);for(int i=1;i<=n;i++)for(int j=f[i]=1;j<i;j++)if(a[j].y<a[i].y && a[j].z<a[i].z){f[i]=max(f[i],f[j]+1);b[j<<1][++b[j<<1][0]]=i<<1|1;}for(int i=1;i<=n;i++){if(f[i]>ans) ans=f[i];f[i]=0;}printf("%d\n",ans),ans=0;for(int i=2;i<=n<<1;i+=2){memset(bz,false,sizeof(bz));if(Hungary(i)) ans++;}printf("%d",n-ans); }

總結

以上是生活随笔為你收集整理的JZOJ 5354. 【NOIP2017提高A组模拟9.9】导弹拦截的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。