洛谷2831 愤怒的小鸟

Luogu

算法

用二进制来表示状态。
那么设$bit[i] [j]$来表示经过猪$i$和$j$能打下来的猪的状态,设$f[S]$表示打到$S$状态最少需要的次数。

很明显:

$f[S|(1<<(i-1))]=min(f[S|(1<<(i-1))],f[S]+1)$
$f[S|bit[i][j]]=min(f[S|bit[i][j]],f[S]+1)$

边界为$f[0]=0$。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
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<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}
inline void write(int x) {
    if (x<0) putchar('-'),x=-x;
    if (x>9) write(x/10);
    putchar(x%10+'0');
}
template<class T> inline void upload(T& a,const T& b) { if (b<a) a=b; } //相当于a=min(a,b)
typedef double db;
const db EPS=1e-7;
const int MAXN=20;
int N,M,T;
int bit[MAXN][MAXN]; //bit[i][j]表示经过猪i和j能打下来的猪的集合
int f[1<<MAXN]; //f[i]表示达到i状态的最小次数
db x[MAXN],y[MAXN];
int main() {
    T=read();
    while (T--) {
        N=read(); M=read();
        for (re int i=1;i<=N;i++) scanf("%lf%lf",&x[i],&y[i]); //输入
        for (re int i=1;i<=N;i++) //预处理bit
            for (re int j=i+1;j<=N;j++) {
                db f=x[i]*x[j]*(x[i]-x[j]);
                db a=x[j]*y[i]-x[i]*y[j];
                db b=x[i]*x[i]*y[j]-x[j]*x[j]*y[i];
                bit[i][j]=0;
                if (a*f<0)
                    for (re int k=1;k<=N;k++)
                        if (fabs(a*x[k]*x[k]+b*x[k]-f*y[k])<EPS)
                            bit[i][j]|=(1<<(k-1));
            }
        memset(f,0x3f,sizeof(f)); f[0]=0; //初始化
        for (re int S=0;S<(1<<N);S++) { //DP
            int i=1;
            while (S&(1<<(i-1))) i++; //找到第一头没打的猪
            upload(f[S|(1<<(i-1))],f[S]+1); //状态转移
            for (re int j=i+1;j<=N;j++) //状态转移
                upload(f[S|bit[i][j]],f[S]+1);
        }
        write(f[(1<<N)-1]); putchar('\n'); //输出
    }
    return 0;
}
最后修改:2019 年 09 月 23 日 10 : 29 PM

发表评论