专栏首页奇妙的算法世界NOIP2016提高组-愤怒的小鸟(状压dp)

NOIP2016提高组-愤怒的小鸟(状压dp)

题意描述

AC代码

#include "iostream"
#include "cstring"
#include "string"
#include "vector"
#include "cmath"
#include "algorithm"
#include "map"
#include "set"
#include "queue"
#include "stack"
#define fi first
#define se second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define seteps(N) setprecision(N)
#define lson (ind<<1)
#define rson (ind<<1|1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef pair<int,int> PII;
typedef pair<char,char> PCC;
typedef pair<double,double> PDD;
typedef pair<ll,ll> PLL;
const int N=25;
const int M=1<<19;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const lll oone=1;
const double eps=1e-6;
const double pi=acos(-1);
int n,m,f[M],path[N][N];
PDD q[N];
int cmp(double x,double y){
    if(abs(x-y)<=eps) return 0;
    if(x<y) return -1;
    return 1;
}
void solve(){
    cin>>n>>m;
    rep(i,0,n) cin>>q[i].fi>>q[i].se;
    mst(path,0);
    rep(i,0,n){
        path[i][i]=1<<i;
        rep(j,0,n){
            double x1=q[i].fi,y1=q[i].se;
            double x2=q[j].fi,y2=q[j].se;
            if(!cmp(x1,x2)) continue;
            double a=(y1/x1-y2/x2)/(x1-x2);
            if(a>=0) continue;
            double b=y1/x1-a*x1;
            int state=0;
            rep(k,0,n){
                double x=q[k].fi,y=q[k].se;
                if(!cmp(a*x*x+b*x,y)) state+=1<<k;
            }
            path[i][j]=state;
        }
    }
    mst(f,INF);
    f[0]=0;
    rep(i,0,(1<<n)-1){
        int x=0;
        rep(j,0,n){
            if(!((i>>j)&1)){
                x=j;
                break;
            }
        }
        rep(j,0,n){
            f[i | path[x][j]]=min(f[i | path[x][j]],f[i]+1);
        }
    }
    cout<<f[(1<<n)-1]<<endl;
}
int main(){
    IOS;
    //freopen("try.in", "r", stdin);
    //freopen("try2.out", "w", stdout);
    int t;cin>>t;
    while(t--)
        solve();
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • E - Knapsack 2 (背包问题变种)

    dejavu1zz
  • I - Coins(dp)

    dejavu1zz
  • codeforces 1437D(思维)

    题目中说每个点的子结点都是升序排列的,并且1结点是父结点,所以我们可以从第二层开始,统计第二层呈升序排列的点的个数,该个数即为第二层的结点数。然后以第二层为基础...

    dejavu1zz
  • hust 1607 Triangles(经典好题)

    题意:给出一定的点,然后再给出哪些点相连,问最后这些相连点的组成多少个三角形,hash的应用 分析:转载牛人的思想 题意:给一些点的坐标和里面的点构成的一些线段...

    用户1624346
  • Neo4j导入思知OwnThink开源的知识图谱

    1.Neo4j database: 4.0.1 (是Neo4j graph数据库版本,非 neo4j desktop版本)

    Sheldon.Lee
  • SecureCRT 8.0安装 & 加载配色方案

    5.开始运行 打开此路径,然后在目录中新建文件夹 keywords,然后将配色方案复制到此目录

    释然
  • malloc与calloc

    Qt君
  • 【玩转腾讯云】使用腾讯云助力知识图谱

    在看到思知开源了1.4亿规模的中文知识图谱数据之后一直想试试对知识图谱的查询。奈何之前的服务器选购的是入门的1核2G学生认证的,不足以支持导入。

    Sheldon.Lee
  • 专访阿里陶辉:大规模分布式系统、高性能服务器设计经验分享

    http://www.csdn.net/article/2014-06-27/2820432

    陶辉
  • 区块链技术(一):Truffle开发入门

    区块链专栏作家 瀚德FinTech创新学院 特邀讲师:汪晓明 ? 芯链项目创始人,朝夕网络CEO。10年互联网技术开发经验。曾参与创立银联大数据、Beltal,...

    企鹅号小编

扫码关注云+社区

领取腾讯云代金券