[NOIP2016]憤怒的小鳥

　　　　　　　　　　　　　　　　　時間限制：1 s?? 內存限制：256 MB

【題目描述】

?

Kiana最近沉迷于一款神奇的游戲無法自拔。

? ?簡單來說，這款游戲是在一個平面上進行的。

? ?有一架彈弓位于(0,0)處，每次Kiana可以用它向第一象限發射一只紅色的小鳥，小鳥們的飛行軌跡均為形如y = ax^2 + bx的曲線，其中a, b是Kiana指定的參數，且必須滿足a<0。

? ?當小鳥落回地面(即x軸)時，它就會瞬間消失。

? ?在游戲的某個關卡里，平面的第一象限中有n只綠色的小豬，其中第i只小豬所在的坐標為(xi,yi)。

? ?如果某只小鳥的飛行軌跡經過了(xi,yi)，那么第i只小豬就會被消滅掉，同時小鳥將會沿著原先的軌跡繼續飛行;

? ?如果一只小鳥的飛行軌跡沒有經過(xi,yi)，那么這只小鳥飛行的全過程就不會對第i只小豬產生任何影響。

? ?例如，若兩只小豬分別位于(1, 3 )和(3, 3 )??

Kiana可以選擇發射一只飛行軌跡為y=-x^2+ 4x的小鳥，這樣兩只小豬就會被這只小鳥一起消滅。

? ?而這個游戲的目的，就是通過發射小鳥消滅所有的小豬。

? ?這款神奇游戲的每個關卡對Kiana來說都很難，所以Kiana還輸入了一些神秘的指令，使得自己能更輕松地完成這個游戲。這些指令將在【輸入格式】中詳述。

? ?假設這款游戲一共有T個關卡，現在Kiana想知道，對于每一個關卡，至少需要發射多少只小鳥才能消滅所有的小豬。由于她不會算，所以希望由你告訴她。

?

【輸出格式】

?

? ?輸出到文件angrybirds.out中。

? ?對每個關卡依次輸出一行答案。

? ?輸出的每一行包含一個正整數，表示相應的關卡中，消滅所有小豬最少需要的小鳥數量。

?

【樣例1輸入】

2 2 0 1.00 3.00 3.00 3.00 5 2 1.00 5.00 2.00 8.00 3.00 9.00 4.00 8.00 5.00 5.00

【樣例1輸出】

1 1

【提示1】

這組數據中一共有兩個關卡。 第一個關卡與【問題描述】中的情形相同，2只小豬分別位于((1.00, 3.00)和(3.00, 3.00)，只需發射一只飛行軌跡為y = -x2 + 4x的小鳥即可消滅它們。 第二個關卡中有5只小豬，但經過觀察我們可以發現它們的坐標都在拋物線y=-x^2+ 6x上，故Kiana只需要發射一只小鳥即可消滅所有小豬。

【樣例2輸入】

3 2 0 1.41 2.00 1.73 3.00 3 0 1.11 1.41 2.34 1.79 2.98 1.49 5 0 2.72 2.72 2.72 3.14 3.14 2.72 3.14 3.14 5.00 5.00

【樣例2輸出】

2 2 3

【樣例3輸入】

1 10 0 7.16 6.28 2.02 0.38 8.33 7.78 7.68 2.09 7.46 7.86 5.77 7.44 8.24 6.72 4.42 5.11 5.42 7.79 8.15 4.99

【樣例3輸出】

6

【提示】

?　　難得今天不考試，找幾道前幾年的NOIP題重新打一下測一下能力。

　　這道題還是挺滿意的，過編譯，過樣例1A，一開始想到的是O(n^2)預處理加O(2^n*n^2)的打法，算著超時，然后就看了一下剪枝，卻發現這樣貌似不加剪枝也能過。

　　這道題數據范圍這么小，應該是搜索或者狀壓，對于狀壓，狀態數組就是f[i]表示把豬打到狀態i所花費的最小代價，那么，我們每在這個基礎上新打一個豬在大多數情況下可以再多帶走一個的，我們可以n^2預處理出來如果我們一次性帶走兩頭指定的豬實際能帶走那些豬，然后轉移就是f[i|link[j][k]]=min(f[i]+1,f[i|link[j][k]])，還是比較容易的，只是要注意，link是保留字，以及煩人的精度問題。

#include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> #include <queue> #include <algorithm> #include <cmath> #include <map> using namespace std; int T,n,m; double x[20],y[20]; int lin[20][20],f[1<<18]; void init(int aa,int bb) {if(fabs(x[aa]-x[bb])-0.0000001<0.0)return;double x1=x[aa],x2=x[bb],y1=y[aa],y2=y[bb];double b=(y2*x1*x1-x2*x2*y1)/(x1*x1*x2-x1*x2*x2);double a=(y1-b*x1)/(x1*x1);if(a-0.00000001<0.0&&fabs(a)-0.0000001>0){lin[aa][bb]=(1<<(aa-1))|(1<<(bb-1));for(int i=1;i<=n;i++){if(i==aa||i==bb)continue;if(abs(a*x[i]*x[i]+b*x[i]-y[i])-0.0000001<0.0){lin[aa][bb]|=(1<<(i-1));}}} } int main() {scanf("%d",&T); while(T--) {memset(lin,0,sizeof(lin));scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%lf%lf",&x[i],&y[i]);}for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){init(i,j);}}memset(f,0xf,sizeof(f));f[0]=0;for(int i=0;i<(1<<n);i++){ for(int j=1;j<=n;j++){if((i&(1<<(j-1)))==0){f[i|(1<<(j-1))]=min(f[i]+1,f[i|(1<<(j-1))]);for(int k=j+1;k<=n;k++){if(lin[j][k]){f[i|lin[j][k]]=min(f[i]+1,f[i|lin[j][k]]);}}}}}printf("%d\n",f[(1<<n)-1]); }return 0; }

　　

轉載于:https://www.cnblogs.com/liutianrui/p/7676218.html

總結

以上是生活随笔為你收集整理的Noip 2016 愤怒的小鸟 题解的全部內容，希望文章能夠幫你解決所遇到的問題。

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