【题解】Luogu P2831 愤怒的小鸟状压dp

桃扇骨 2023-08-17 16:49 93阅读 0赞

## 状压dp ##

--------------------

思路来自[@real\_l][real_l]

由于抛物线$y=a\*\{x^2\}+b\*y$只有两个参数，初中数学老师告诉我们代入两个点的坐标就能求得解析式

$$\{a\*\{ \{x\_1\}^2\}+b\*\{y\_1\}=y\}$$

$$\{a\*\{ \{x\_2\}^2\}+b\*\{y\_2\}=y\}$$

可以得到

$$\{a=(x\_2\*y\_1-x\_1\*y\_2)/(\{x\_1\}^2\*\{x\_2\}-\{x\_2\}^2\*\{x\_1\})\}$$

$$\{b=(\{x\_1\}^2\*y\_2-\{x\_2\}^2\*y\_1)/(\{x\_1\}^2\*x\_2-\{x\_2\}^2\*x\_1)\}$$

l\[i\]\[j\]存抛物线和线上的猪

状态转移方程 f\[k|l\[i\]\[j\]\]=min(f\[k|l\[i\]\[j\]\],f\[k\]+1)

code

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 namespace gengyf{
     4 #define ll long long
     5 const double eps=1e-8;
     6 inline int read(){
     7     int x=0,f=1;
     8     char c=getchar();
     9     while(c<'0'||c>'9'){
         if(c=='-')f=-1;c=getchar();}
    10     while(c>='0'&&c<='9'){x=(x*10)+c-'0';c=getchar();}
    11     return x*f;
    12 }
    13 int n,m,t,l[20][20],lowbit[1<<20],f[1<<20];
    14 double x[20],y[20];
    15 void equation(double &x,double &y,double a1,double b1,double c1,double a2,double b2,double c2){
    16     y=(a1*c2-a2*c1)/(a1*b2-a2*b1);
    17     x=(c1-b1*y)/a1;
    18 }
    19 void init(){
    20     for(int i=0;i<(1<<18);i++){
    21         int j=1;
    22         for(;j<=18 && i&(1<<(j-1));j++);
    23         lowbit[i]=j;
    24     }
    25 }
    26 int main(){
    27     init();
    28     t=read();
    29     while(t--){
    30         memset(l,0,sizeof(l));
    31         memset(f,0x3f,sizeof(f));
    32         f[0]=0;
    33         scanf("%d%d",&n,&m);
    34         for(int i=1;i<=n;i++){
    35             scanf("%lf%lf",x+i,y+i);
    36         }
    37         for(int i=1;i<=n;i++)
    38             for(int j=1;j<=n;j++){
    39                 if(fabs(x[i]-x[j])<eps) continue;
    40                 double a,b;
    41                 equation(a,b,x[i]*x[i],x[i],y[i],x[j]*x[j],x[j],y[j]);
    42                 if(a>-eps) continue;
    43                 for(int k=1;k<=n;k++)
    44                     if(fabs(a*x[k]*x[k]+b*x[k]-y[k])<eps){
    45                         l[i][j]|=(1<<(k-1));
    46                     }
    47             }
    48         for(int i=0;i<(1<<n);i++){
    49             int j=lowbit[i];
    50             f[i|(1<<(j-1))]=min(f[i|(1<<(j-1))],f[i]+1);
    51             for(int k=1;k<=n;k++){
    52                 f[i|l[j][k]]=min(f[i|l[j][k]],f[i]+1);
    53             }
    54         }
    55         printf("%d\n",f[(1<<n)-1]);
    56     }
    57     return 0;
    58 }
    59 }
    60 signed main(){
    61   gengyf::main();
    62   return 0;
    63 }

转载于:https://www.cnblogs.com/gengyf/p/11586314.html

[real_l]: https://www.cnblogs.com/real-l/p/9157479.html
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230809/c876a79a37084abc90e992ab8d532628.png