[NOIP2016 提高組] 憤怒的小鳥

題意：

有n只豬，給出豬的坐標(xi,yi),問最少用幾個形如 y=ax^2+bx 的曲線可以保證所有豬在曲線上，滿足a<0,a,b為實數
n<=18,

題解：

兩個方法：爆搜或者狀壓dp

狀壓dp

看n<=18也就能看出來，這數據范圍就是用狀壓dp
我們用二進制來表示哪些豬已經被曲線標記，比如11(十進制)，二進制下是000001011，表示第1，2，4頭豬已經被標記
首先對于每個狀態，我們用state[i]記錄其第一次0出現的位置（從右往左），這將作為我們dp的起點

for(int i=0;i<(1<<18);i++){int j=1;for(;j<=18 && i&(1<<(j-1));j++);start[i]=j;//記錄該狀態下，出現第一個0的位置 }

然后我們枚舉兩個點帶入到式子y=ax^2+bx，求出a和b,a必須大于0，然后枚舉所有點，看哪些點在這個拋物線上，用line[i][j]來記錄能經過哪些豬🐖
然后對于每一種狀態，起點就是我們之前求的0的第一次位置，然后枚舉其他點x，x有可能在拋物線上，也有可能單獨成拋物線，取最小
詳細看代碼

爆搜

參考題解
對于每個豬，如果他不能存在于之前的拋物線，就與其他豬構成拋物線，然后繼續搜。還有一種選擇：暫時不與其它豬組成拋物線
代碼里有大量詳細的注釋

代碼：

狀壓dp

#include<bits/stdc++.h> using namespace std; const double eps=1e-8; int T,n,m,lines[19][19],start[1<<19],dp[1<<19]; double x[19],y[19]; void equation(double &a,double &b,int i,int j){a=-(y[i]*x[j]-y[j]*x[i])/(x[j]*x[j]*x[i]-x[i]*x[i]*x[j]);b=(y[i]*x[j]*x[j]-y[j]*x[i]*x[i])/(x[i]*x[j]*x[j]-x[j]*x[i]*x[i]); } int main(){for(int i=0;i<(1<<18);i++){int j=1;for(;j<=18 && i&(1<<(j-1));j++);start[i]=j;//記錄該狀態下，出現第一個0的位置 }scanf("%d",&T);for(int i=1;i<=T;i++){memset(lines,0,sizeof(lines));memset(dp,1,sizeof(dp));dp[0]=0;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=1;j<=n;j++){if(fabs(x[i]-x[j])<eps) continue;//橫坐標相等 double a,b;equation(a,b,i,j);if(a>-eps) continue;//必須開口向下 for(int k=1;k<=n;k++)//枚舉被拋物線經過的點 if(fabs(a*x[k]*x[k]+b*x[k]-y[k])<eps)lines[i][j]|=(1<<(k-1));}for(int i=0;i<(1<<n);i++){int j=start[i];dp[i|(1<<(j-1))]=min(dp[i|(1<<(j-1))],dp[i]+1); for(int k=1;k<=n;k++)dp[i|lines[j][k]]=min(dp[i|lines[j][k]],dp[i]+1); }printf("%d\n",dp[(1<<n)-1]);}return 0; }

爆搜代碼：

/*思路：搜索。 對于第i只豬，如果它已經被前面所構造的某條拋物線經過了， 就不用處理了，繼續往下搜索。否則，就有兩種選擇，第一種 是與前面某一只單獨的豬（即這只豬未與其它豬組成拋物線） 組成拋物線，因為兩只豬最多也只能被一條拋物線相連；第二 種是暫時不與其它單獨的豬組成拋物線。最后，將拋物線的條 數與余下的豬的個數相加（因為單獨的一只豬也要一條拋物線 將其擊中）就是搜索出來的一個合法的結果。*/ #include<iostream> #include<cstdio> #include<fstream> #include<algorithm> #include<string> #include<sstream> #include<cstring> #include<cmath>using namespace std;const double eps=1e-8; /*因為浮點數的精度計算太過復雜，像3.14這樣的數存在浮 點型變量里存的可能是3.139999999，也有可能是3.140000001， 所以不能直接用“==”判斷兩個浮點數是否相等。在這種情況 下，就允許判斷兩個浮點數為相等時，兩數之間存在微小的誤差， 這個“微小的誤差”要取一個較小的數，比如1e-8，這樣就不 會判不出也不會誤判了。*/ bool dy(double a,double b)//判斷兩個浮點數是否相等的函數 {//如果a和b之間相差的值小于eps（即1e-8），就說明它們是相等的 return fabs(a-b)<eps;//fabs用于取浮點數的絕對值 }int n=0,m=0,ans=0;//x數組存每只豬的x坐標，y數組存每只豬的y坐標//pwxa數組存每條已構造的拋物線的參數a，pwxb數組存每條已構造的拋物線的參數b//tx數組存每只單獨的豬的x坐標，ty數組存每只單獨的豬的y坐標 double x[20],y[20],pwxa[20],pwxb[20],tx[20],ty[20]; //dfs(c,u,v)表示當前搜到第c只豬，已構造拋物線的數量為u，單獨的豬的數量為v時的情況 //注意：當前拋物線的總數量為(u+v)條，因為除已有的拋物線外，每一只單獨的豬也需要一條拋物線來擊中它 void dfs(int c,int u,int v) {//最優性剪枝，因為即使后面的每一只豬都被當前已構造的拋物線擊中， //或者與其它單獨的豬組成拋物線，拋物線的總數量還是(u+v)，不會減少，//所以如果拋物線的總數量已經大于等于當前的最優解時，搜下去也不會//比當前更優了，就不用繼續搜下去了。if(u+v>=ans) return;if(c>n)//如果搜完了 {ans=u+v;//記錄答案，因為前面已經有最優性剪枝了，所以沒被剪掉的答案一定比當前更優 return;//結束 }bool flag=false;//記錄是否被已構造的拋物線經過 for(int i=1;i<=u;i++)//枚舉已構造的拋物線 //將這一條拋物線的參數與當前豬的x坐標帶進函數解析式算一遍，//如果結果等于當前豬的y坐標，就說明當前豬已經被已構造的拋物線經過了 if(dy(pwxa[i]*x[c]*x[c]+pwxb[i]*x[c],y[c])){dfs(c+1,u,v);//被經過了就直接往下搜 flag=true;//記錄 break;//退出循環，既然當前豬已經被經過了，再繼續判斷也沒有意義了}if(!flag)//如果沒有被經過 {for(int i=1;i<=v;i++)//枚舉單獨的豬 {//如果當前豬與這一只單獨的豬的x坐標相同，就說明它們不能組成一條//拋物線。因為若想使它們組成一條拋物線，彈弓的位置就必須是它們的正下//方，然后往上垂直發射，但是彈弓的位置固定在(0,0)，而豬的x坐標又大于//0（題目數據范圍），所以它們不能組成一條拋物線。如果不加這個判//斷的話就會計算出一些奇奇怪怪的東西，影響后面的判斷，所以還是加上為好。 if(dy(x[c],tx[i])) continue;//如果當前豬與這一只單獨的豬的x坐標相同，跳過這一次循環//求參數a、b的過程實際上就是解一個二元一次方程組，比如說有兩只豬的坐標分別是(1,3)和(3,3)， //現在要求出它們所組成的拋物線的參數a與參數b。將兩只豬的坐標分別代入到函數解析式中，//就可以得出一個方程組： 3=a+b 3=9a+3b 。這是，我們可以用加減消元法消掉b，將兩個方程//分別乘上另一個方程的b的系數，得：9=3a+3b 3=9a+3b。這樣，兩個方程中的b的系數就一致了，//然后直接用一個式子減去另一個式子，再將a的系數化為一即可。最后再將a帶入到回任意一個方程求b即可。//因為這里的所有方程都長一個樣，所以這一種方法是通用的。 double a=(y[c]*tx[i]-ty[i]*x[c])/(x[c]*x[c]*tx[i]-tx[i]*tx[i]*x[c]);//求參數a double b=(y[c]-x[c]*x[c]*a)/x[c];//將a代入求參數b if(a<0)//如果這一個解是合法的，就說明當前豬與這一只單獨的豬可以組成拋物線 { pwxa[u+1]=a;//記錄拋物線的參數a pwxb[u+1]=b;//記錄拋物線的參數b//將這一只單獨的豬從數組中刪去，因為它已經和當前豬組成拋物線，不再單獨了 double q=tx[i],w=ty[i];for(int j=i;j<v;j++){tx[j]=tx[j+1];ty[j]=ty[j+1];}dfs(c+1,u+1,v-1);//繼續往下搜//將這一只單獨的豬放回數組（回溯） for(int j=v;j>i;j--) {tx[j]=tx[j-1];ty[j]=ty[j-1];}tx[i]=q;ty[i]=w;}}//還有一種選擇：暫時不與其它豬組成拋物線 tx[v+1]=x[c];ty[v+1]=y[c];dfs(c+1,u,v+1);//繼續往下搜 } } int main() {int T=0;scanf("%d",&T);for(int Q=1;Q<=T;Q++){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%lf%lf",&x[i],&y[i]);ans=100;//記得初始化 dfs(1,0,0);//搜 printf("%d\n",ans); } return 0;//完美地結束 } //借鑒大神之作 //完美爆搜

總結

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

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