Luogu

分析

现在做感觉好傻逼啊 QAQ

我们先预处理出一个 $bit_{i,j}$,表示 $i,j$ 两只猪构成的抛物线上的猪的状态。这个东西根据初中数学知识解出 $a,b$ 再代进去算一下就好了。

设 $dp_S$ 表示打完 $S$ 中的猪最少需要多少次,转移枚举打掉哪两只猪就好了。

然后这样是 $\mathcal{O}(Tn^22^n)$ 的,考虑一个优化。因为 $S$ 中编号最小的那只猪是无论如何要打掉的,所以我们钦定这次打掉它,复杂度降为 $\mathcal{O}(Tn2^n)$。

另外写了这题一定要去 UOJ 感受一下被卡精度的快乐

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
using namespace std;

inline void chkmin(int& x,int y) { if (y<x) x=y; }
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=18+10;

int n,cnt;
double x[N],y[N];
int bit[N][N],dp[1<<19];

int main() {
    int T=read();
    while (T--) { cnt=0;
        n=read(),read();
        for (re int i=1;i<=n;++i) scanf("%lf%lf",&x[i],&y[i]);
        for (re int i=1;i<=n;++i)
            for (re int j=i+1;j<=n;++j) {
                bit[i][j]=0;
                double a=(x[j]*y[i]-x[i]*y[j])/(x[i]*x[j]*(x[i]-x[j]));
                double b=(x[i]*x[i]*y[j]-x[j]*x[j]*y[i])/(x[i]*x[j]*(x[i]-x[j]));
                if (a<-1e-6) {
                    for (re int k=1;k<=n;++k)
                        if (fabs(a*x[k]*x[k]+b*x[k]-y[k])<1e-12)
                            bit[i][j]|=(1<<(k-1));
                }
            }
        memset(dp,0x3f,sizeof(dp)); dp[0]=0;
        for (re int S=0;S<(1<<n);++S) { int i;
            for (i=1;S&(1<<(i-1));++i);
            chkmin(dp[S|(1<<(i-1))],dp[S]+1);
            for (re int j=i+1;j<=n;++j)
                chkmin(dp[S|bit[i][j]],dp[S]+1);
        }
        printf("%d\n",dp[(1<<n)-1]);
    }
    return 0;
}
最后修改:2019 年 10 月 31 日 05 : 25 PM