題目

我的天，這題是真的卡精度......

主要是精度很不好處理，經本蒟蒻測驗，精度在\(10^{-6}\)會比較好優雅

---

【分析】

對于這種某個變量特別小\((\leq 31)\)的題目，本蒟蒻第一反應就是狀壓

對于某個拋物線，一定要打到起碼一個小豬(不然不如不要這一條拋物線)

有人覺得最少會打掉兩只小豬的，可以仔細想一下，萬一\(a \geq 0\)呢......

好的，我們繼續

那么，我們可以這么考慮，枚舉每一只小豬的坐標

首先，有一條拋物線是只過它的

其次，再枚舉其他小豬，算出拋物線方程(見下方)，若\(a<0\)就記錄這條拋物線，否則可以直接跳出

記錄完這條拋物線后，我們枚舉其他的小豬，查看是否在線上

這里要注意精度問題，如果計算出來的\(y\)與題目所給的\(y\)偏差值不超過\(10^{-6}\)，就直接視為同一個值(畢竟計算是有一定的精度問題)

那么對于接下來，我已經預處理過了所有的小鳥的軌跡(拋物線)，只需要在狀壓方程中直接算就可以了

在打\(0\)只小豬的時候，需要用\(0\)只小鳥，于是有:

\(dp[0]=0\)

假設當前狀態為\(i\)，拋物線為第\(j\)條，拋物線打掉的小豬狀態為\(para[j]\)，那么有：

\(dp[i|para[j]]=min(dp[i|para[j]],dp[i]+1)\)

---

接下來我們說一下怎么求\(a\)和\(b\):

假設枚舉到兩個小豬，坐標分別為\((x_1,y_1)\)和\((x_2,y_2)\)，那么就對應地會有：

\(\begin{cases} y_1=ax_1^2+bx_1\\ \\y_2=ax_2^2+bx_2\end{cases}\)

這里有一個很明顯的矩陣關系：

\(\left[\begin{matrix}\ y_1\ \\ \\y_2\end{matrix}\right]=\left[\begin{matrix}\ x_1^2&x_1\ \\ \\x_2^2&x_2\end{matrix}\right]\times\left[\begin{matrix}\ a\ \\ \\b\end{matrix}\right]\)

于是有：

\(\left[\begin{matrix}\ a\ \\ \\b\end{matrix}\right]=\left[\begin{matrix}\ x_1^2&x_1\ \\ \\x_2^2&x_2\end{matrix}\right]^{-1}\times\left[\begin{matrix}\ y_1\ \\ \\y_2\end{matrix}\right]\)

又因為：

\(\left|\begin{matrix}\ x_1^2&x_1\\ \\x_2^2&x_2\end{matrix}\right|=x_1^2x_2-x_1x_2^2=(x_1-x_2)x_1x_2\)

所以有：

\(\left[\begin{matrix}\ x_1^2&x_1\ \\ \\ x_2^2&x_2\end{matrix}\right]^{-1}=\frac{1}{(x_1-x_2)x_1x_2}\left[\begin{matrix}\ x_2&-x_1\ \\ \\-x_2^2&x_1^2\end{matrix}\right]\)

(逆矩陣的求法)

所以有：

\(\left[\begin{matrix}\ a\ \\ \\b\end{matrix}\right]={1\over(x_1-x_2)x_1x_2}\left[\begin{matrix}\ x_2&-x_1\ \\ \\-x_2^2&x_1^2\end{matrix}\right]\times\left[\begin{matrix}\ y_1\ \\ \\y_2\end{matrix}\right]\)

即：

\(\begin{cases}a={1\over(x_1-x_2)x_1x_2}\times(x_2y_1-x_1y_2)\\ \\b={1\over(x_1-x_2)x_1x_2}\times(x_1^2y_2-x_2^2y_1)\end{cases}\)

---

還有一件事

我們對于拋物線，在后面枚舉狀態的時候是不需要知道除了能打的小豬以外的所有信息

所以直接維護這個信息就可以了，其他都沒有必要維護

這個眾位大犇可以直接一下本蒟蒻的代碼

---

【代碼】

那本蒟蒻就放代碼了：

#include<cstdio>

#include<cstring>

using namespace std;

#define min(a,b) ((a<b)?a:b)

inline void built(double &a,double &b,double x1,double y1,double x2,double y2){

    a=(x2*y1-x1*y2)/(x1*x2*(x1-x2));

    b=(x1*x1*y2-x2*x2*y1)/(x1*x2*(x1-x2));

}//計算a,b

inline bool inc(double a,double b,double x,double y){

	double abs=a*x*x+b*x-y;

	if(abs<0) abs=-abs;

	return abs<=0.000001;

}//判定某個小豬是否在拋物線上

inline int read(){

	int ans=0;char c=getchar();bool neg=0;

	while((c<'0')|(c>'9')) { neg^=!(c^'-'); c=getchar(); }

	while((c>='0')&(c<='9')) { ans=(ans<<3)+(ans<<1)+c-'0'; c=getchar(); }

	return neg?-ans:ans;

}//無聊的讀入優化

int n,para[200],dp[1<<18],countpara;

inline void pre(){

	memset(dp,0x3f,sizeof(dp));

	countpara=0;

	double x[18]={0},y[18]={0};

	n=read();read();

	for(int i=0;i<n;i++) scanf("%lf %lf",&x[i],&y[i]);

	//dp定義為無限大，拋物線的條數清空，讀入

	for(int i=0;i<n;i++){

		para[countpara++]=(1<<i);

		//只打一只小豬的

		for(int j=i+1,vis=0;j<n;j++)//定義vis表示打到過的小豬，避免重復枚舉

			if((vis>>j)&1) continue;

			else{

				double a,b;

				built(a,b,x[i],y[i],x[j],y[j]);

				if(a>=0) continue;

				para[countpara]=(1<<i);

				for(int k=j;k<n;k++)//枚舉小豬，查看是否在線上

					if(inc(a,b,x[k],y[k])){

						vis|=(1<<k);

						para[countpara]|=(1<<k);

					}

				countpara++;

			}

	}

}

inline int ans(){//狀壓

	dp[0]=0;

	for(int i=0;i<(1<<n);i++)

		for(int j=0;j<countpara;j++)

			dp[i|para[j]]=min(dp[i|para[j]],dp[i]+1);

	return dp[(1<<n)-1];

}

int main(){

	int t=read();

	while(t--){

		pre();//先皮一下

		printf("%d\n",ans());

	}

	return 0;

}

最后安利一下 本蒟蒻的博客

總結

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

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