愤怒的小鸟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; }
上一篇: 封装axios并创建请求函数
下一篇: 古色古香