當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

愤怒的小鸟（爆搜，剪枝）

發布時間：2025/6/17 编程问答 34 豆豆

生活随笔收集整理的這篇文章主要介紹了愤怒的小鸟（爆搜，剪枝）小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

題目描述

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

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

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

當小鳥落回地面（即?

在游戲的某個關卡里，平面的第一象限中有? $nn?只綠色的小豬，其中第?ii?只小豬所在的坐標為?\left(x_i,y_i \right)(xi?,yi?)?。$

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

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

例如，若兩只小豬分別位于? $(1,3)(1,3)?和?(3,3)(3,3)?，Kiana?可以選擇發射一只飛行軌跡為?y=-x^2+4xy=?x2+4x?的小鳥，這樣兩只小豬就會被這只小鳥一起消滅。$

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

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

假設這款游戲一共有?

輸入輸出格式

輸入格式：

第一行包含一個正整數?

下面依次輸入這? $輸入的神秘指令類型。接下來的?nn?行中，第?ii?行包含兩個正實數?x_i,y_ixi?,yi??，表示第?ii?只小豬坐標為?(x_i,y_i)(xi?,yi?)?。數據保證同一個關卡中不存在兩只坐標完全相同的小豬。$

如果?

如果? $m=1m=1?，則這個關卡將會滿足：至多用?\lceil n/3 + 1 \rceil?n/3+1??只小鳥即可消滅所有小豬。$

如果? $m=2m=2?，則這個關卡將會滿足：一定存在一種最優解，其中有一只小鳥消滅了至少?\lfloor n/3 \rfloor?n/3??只小豬。$

保證? $1\leq n \leq 181≤n≤18?，?0\leq m \leq 20≤m≤2?，?0 < x_i,y_i < 100<xi?,yi?<10?，輸入中的實數均保留到小數點后兩位。$

上文中，符號? $\lceil c \rceil?c??和?\lfloor c \rfloor?c??分別表示對?cc?向上取整和向下取整，例如：?\lceil 2.1 \rceil = \lceil 2.9 \rceil = \lceil 3.0 \rceil = \lfloor 3.0 \rfloor = \lfloor 3.1 \rfloor = \lfloor 3.9 \rfloor = 3?2.1?=?2.9?=?3.0?=?3.0?=?3.1?=?3.9?=3?。$

輸出格式：

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

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

思路：

沒什么好說的。。。只能%%一群狀壓大佬

我是這么想的，一個豬被打掉，要么是單獨的一只小鳥干的

要么是被一只路過的小鳥干的

那么，在經過一個沒有被打掉的豬的時候，將這個豬與其他沒有打掉的豬嘗試配對

算出一條拋物線，看這條路上能打掉幾只豬，并打標記

當然，也可以不算拋物線，默認用一只鳥打掉

加一個最優化剪枝即可

（ps 注意精度）

代碼：

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #define rii register int i #define rij register int j #define inf 19260817 #define eps 0.0000001 using namespace std; int n,m,t,ans; struct pw{double a,b; }pwx[20]; struct pig{double x,y; }zb[20]; double bjx[20],bjy[20]; inline pw echs(int wz,int i) {pw an;double lzn=zb[wz].x;double rxz=zb[wz].y;double ltt=(rxz*bjx[i]-bjy[i]*lzn);ltt/=(lzn*lzn*bjx[i]-bjx[i]*bjx[i]*lzn);double kkk=(rxz-lzn*lzn*ltt)/lzn;an.a=ltt;an.b=kkk;return an; } void dfs(int wz,int sl,int sy) {if(sl+sy>=ans){return;}if(wz>=n+1){ans=sl+sy;return;}int pd=0;for(rii=1;i<=sl;i++){if(fabs(pwx[i].a*zb[wz].x*zb[wz].x+pwx[i].b*zb[wz].x-zb[wz].y)<=eps){dfs(wz+1,sl,sy);pd=1;break;}}if(pd!=1){for(rii=1;i<=sy;i++){if(fabs(zb[wz].x-bjx[i])<eps){continue;}pw kk=echs(wz,i);if(kk.a<0){ pwx[sl+1]=kk;double ltt=bjx[i];double kkk=bjy[i];for(rij=i;j<sy;j++){bjx[j]=bjx[j+1];bjy[j]=bjy[j+1];}dfs(wz+1,sl+1,sy-1);for(rij=sy;j>i;j--) {bjx[j]=bjx[j-1];bjy[j]=bjy[j-1];}bjx[i]=ltt;bjy[i]=kkk;}}bjx[sy+1]=zb[wz].x;bjy[sy+1]=zb[wz].y;dfs(wz+1,sl,sy+1);} } int main() {scanf("%d",&t);for(rii=1;i<=t;i++){scanf("%d%d",&n,&m);for(rij=1;j<=n;j++){scanf("%lf%lf",&zb[j].x,&zb[j].y);}ans=inf;dfs(1,0,0);printf("%d\n",ans); } }

轉載于:https://www.cnblogs.com/ztz11/p/9401434.html

總結

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

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

上一篇： Python有趣现象（不定时更新）
下一篇： dubbo与springboot的集成