P2831 愤怒的小鸟——状压
2024-08-27 10:27:34
抛物线过原点,只要再找两个就能确定抛物线;
处理出两两之间的抛物线能过哪些点,状态压缩;
但是直接枚举每一条抛物线常数太大会T,所以我们需要预处理一个low_bit表示当前状态下第一个没选的,即是二进制下第一个不是1的位置;
因为我们早晚都要把它变成1,所以先处理他就可以达到要求;
注意精度问题;
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef double dd;
const int maxn=;
const dd acc=1e-; int T,n,m;
dd x[maxn],y[maxn]; int low_bit[<<]; int line[maxn][maxn]; void check(dd&a,dd &b,dd x1,dd y1,dd x2,dd y2)
{
a=(y1*x2-y2*x1)/(x1*(x1*x2-x2*x2));
b=(y2-a*x2*x2)/x2;
} int f[<<]; int main()
{
for(int i=;i<<<;i++)
{
int j=;
for(;j<=&& i&(<<(j-));j++);
low_bit[i]=j;
//printf("!!%d\n",low_bit[i]);
} scanf("%d",&T); while(T--)
{
memset(f,0x3f,sizeof(f));
memset(line,,sizeof(line));
f[]=;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
{
scanf("%lf%lf",&x[i],&y[i]);
} for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
{
if(fabs(x[i]-x[j])<acc) continue;
dd a,b;
check(a,b,x[i],y[i],x[j],y[j]);
//printf("!!\n");
//printf("%lf %lf\n",a,b);
if(a>-acc) continue;
for(int k=;k<=n;k++)
{
if(fabs(a*x[k]*x[k]+b*x[k]-y[k])<acc)
{
line[i][j]|=<<(k-);
//printf("!!%d\n",line[i][j]);
}
}
}
} for(int i=;i<(<<n);i++)
{
int j=low_bit[i];
//printf("!?%d\n",j);
f[i|(<<(j-))]=min(f[i]+,f[i|(<<(j-))]);
//printf("??%d\n",f[i|(1<<(j-1))]);
for(int k=;k<=n;k++)
{
f[i|line[j][k]]=min(f[i]+,f[i|line[j][k]]);
}
} printf("%d\n",f[(<<n)-]);
} return ;
}
最新文章
- storm基础系列之五---------接入数据收集系统flume
- [转]Zookeeper原理及应用场景
- css之overflow:细探之下有意想不到的结果
- 反射认识_06_ArrayList_HashSet区别
- C# WinForm程序添加引用后调用静态方法时报“Interfaces_Helper.Global”的类型初始值设定项引发异常。--->; System.NullReferenceException: 未将对象引用设置到对象的实例。
- 【转】HTTP HEAD
- Codeforces Round #327 (Div. 2) E. Three States BFS
- iOS 沙盒目录结构介绍
- php phalcon
- selenium3.7+ python3 添加cookie模拟登陆
- web报表工具FineReport常用函数的用法总结(日期和时间函数)
- ArcGIS 批量修改数据名称-arcgis案例实习教程
- 基于STM32L4的开源NBIOT开发资料
- hdu5001 Walk 概率DP
- Wannafly 挑战赛22 D 整数序列 线段树 区间更新,区间查询
- Texas Instruments matrix-gui-2.0 hacking -- menubar.php
- swap分区和内存
- Python流程控制-while循环-for循环
- 在IE7+ 中弹出窗口并关闭本身窗口的脚本(备忘)
- LevelDB SSTable文件