欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

愤怒的小鸟P2831

程序员文章站 2022-07-04 09:26:17
题意: 有 n 个坐标,求用抛物线 y=ax^2+bx 将它们全部穿过所需的最少个数 思路: 状压dp 另外对于被同一条抛物线穿过的两点,有: a=(x2y1-x1y2)/(x1x2(x1-x2), b=(x1x1y2-x2x2y1)/(x1x2*(x1-x2)) code: ......

 题意: 

      有 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;
}