正題

題目鏈接:https://www.luogu.com.cn/problem/P2831

---

題目大意

$n$個點，每次可以射掉在函數$y=a{x}^2+bx$上的點（$a,b$自定但是要求$a<0$）。求最少射擊次數。

---

解題思路

考慮狀壓，我們發現如果一次射掉兩個或以上的點那么一定是一條固定的線（如果$a\ge 0$的話就沒有了）。計算$cove{r}_{i,j}$表示如果同時射掉$i$和$j$會射掉的點集。

這樣就是$O(T{2}^n{n}^2)$的，無法勝任本題，考慮如何優化。

我們發現對于一個在目前狀態中沒有射掉的點$x$，如果先射掉別的點再射掉他其實是一樣的。所有我們固定每次先射掉編號最小的沒有射掉的點即可。時間復雜度$O(T{2}^{n}n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int N=20; const double eps=1e-8; int T,n,m,MS,f[1<<N],cover[N][N]; double a,b,x[N],y[N]; void solve(double a1,double b1,double c1,double a2,double b2,double c2){b=(c1/a1-c2/a2)/(b1/a1-b2/a2);a=c1/a1-b1/a1*b;return; } int main() {scanf("%d",&T);while(T--){memset(f,0x3f,sizeof(f));scanf("%d%d",&n,&m);for(int i=0;i<n;i++)scanf("%lf%lf",&x[i],&y[i]);memset(cover,0,sizeof(cover));for(int i=0;i<n;i++)for(int j=0;j<n;j++){if(fabs(x[i]-x[j])<eps)continue;solve(x[i]*x[i],x[i],y[i],x[j]*x[j],x[j],y[j]);if(a>-eps)continue;for(int k=0;k<n;k++)if(fabs(y[k]-(a*x[k]*x[k]+b*x[k]))<eps)cover[i][j]|=(1<<k);}MS=1<<n;f[0]=0;for(int i=0;i<MS;i++){int x;for(x=0;x<n;x++)if(!((i>>x)&1))break;f[i|(1<<x)]=min(f[i|(1<<x)],f[i]+1);for(int j=0;j<n;j++)f[i|cover[x][j]]=min(f[i|cover[x][j]],f[i]+1);}printf("%d\n",f[MS-1]);} }

總結

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

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