NOIP2016 愤怒的小鸟

状态压缩DP

 

 

 

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#define Inf 2139062143
#define N 24
using namespace std;

double x[N], y[N];
int T, n, m, f[1 << 19], s[N][N];

//判断x与y是否相等 
bool judge(double x, double y ){
    return (fabs(x - y) < 1e-9);
}

//计算第i点与第j点的抛物线方程即状态
//s[i][j]值的含义 二进制意义下能打下的小鸟如值为5，表示打下第1和第3个小鸟 
void work(int i, int j) {
    if (i == j) {
        s[i][j] = 1 << (i - 1);
        return;
    }

    double a = (y[i] * x[j] - y[j] * x[i]) / (x[i] * x[j] * (x[i] - x[j]));
    double b = y[i] / x[i] - (y[i] * x[j] - y[j] * x[i]) / (x[j] * (x[i] - x[j]));
    if (a >= 0) return;

	//合并本抛物线能打下的全部小鸟 
    int ts = 0;
    for (int g = 1; g <= n; ++g) {
        double tmp = a * x[g] * x[g] + b * x[g];
        if (judge(tmp, y[g])) ts |= (1 << (g - 1));
    }

    s[i][j] = ts;
}

int main() {
    freopen("in.txt", "r", stdin);
    scanf("%d", &T);
    while (T--) {
        memset(f, 127, sizeof(f));
        memset(s, 0, sizeof(s));
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; ++i) {
            scanf("%lf%lf", &x[i], &y[i]);
        }
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                work(i, j);
                
        f[0] = 0;
        for (int i = 0; i < (1 << n) - 1; ++i)  //枚举状态 
        
            for (int j = 1; j <= n; ++j) {  //枚举每个小鸟 
                if (i & (1 << (j - 1))) continue; //状态i已经可以打下小鸟j则直接枚举下一小鸟 
                
                //状态i不包含小鸟j，则把小鸟j合并到某个抛物线上 
                for (int k = 1; k <= n; ++k) { //计算与每个小鸟合并，得到最小值 
                    if (i & (1 << (k - 1))) continue;
                    f[i | s[j][k]] = min(f[i | s[j][k]], f[i] + 1);
                }
                break;
            }
        printf("%d\n", f[(1 << n) - 1]);
    }
    return 0;
}