首页 > > 程序设计 > C/C++ >

愤怒的小鸟P2831

2018-07-24 07:50:49来源：博客园阅读 ()

题意：

有 n 个坐标，求用抛物线 y=ax^2+bx 将它们全部穿过所需的最少个数

思路：

状压dp 另外对于被同一条抛物线穿过的两点，有： a=(x2y1-x1y2)/(x1x2(x1-x2), b=(x1x1y2-x2x2y1)/(x1x2*(x1-x2))

code：

#include <cstdio>
#include <cstring>
#include <algorithm> 
using namespace std;
int n, m, t, p[200], dp[1<<18], cnt;
void solve(double &a, double &b, double x1, double y1, double x2, double y2){
    a = (x2 * y1 - x1 * y2) / (x1 * x2 * (x1 - x2));
    b = (x1 * x1 * y2 - x2 * x2 * y1) / (x1 * x2 * (x1 - x2)); 
} 
bool inc(double a, double b, double x, double y){
    double abs = a * x * x + b * x - y;
    if (abs < 0) abs = -abs;
    return abs <= 0.000001;
} 
void pre(){
    for (int i = 0; i <= (1<<18); i++) dp[i] = 0xffffff;
    cnt = 0;
    double x[20], y[20];
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++) scanf("%lf%lf", &x[i], &y[i]);
    for(int i = 0; i < n; i++) {
        p[cnt++] = (1<<i);
        for(int j = i + 1, vis = 0; j < n; j++)
            if((vis>>j) & 1) continue; // 不能增加打掉的猪   
            else{
                double a, b;
                solve(a, b, x[i], y[i], x[j], y[j]);
                if(a >= 0) continue;
                p[cnt] = (1<<i);
                for(int k = j; k < n; k++)
                    if(inc(a, b, x[k], y[k])){
                        vis |= (1<<k);
                        p[cnt] |= (1<<k); //01000101 表示能打1 3 7 这三只猪   
                    }
                cnt++;
            }
    }
}
int ans(){
    dp[0] = 0;
    for(int i = 0; i < (1<<n); i++)
        for(int j = 0; j < cnt; j++)
            dp[i | p[j]] = min(dp[i | p[j]], dp[i] + 1);//选取该条抛物线 或者加一条  
    return dp[(1<<n) - 1];
}
int main(){
    scanf("%d", &t);
    while(t--){
        pre();
        printf("%d\n", ans()); 
    }
    return 0;
}