重力坠击

思路

• 先把所有点为圆心的攻击范围能够消灭敌人的情况用二进制存下来（状态压缩，消灭用1表示），并去重
• 在这种几种情况从中选取k种，求消灭了敌人的人数<===> 二进制中1的个数

代码

// Problem: 重力坠击
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/9983/C
// Memory Limit: 524288 MB
// Time Limit: 4000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp(aa,bb) make_pair(aa,bb)
#define _for(i,b) for(int i=(0);i<(b);i++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,b,a) for(int i=(b);i>=(a);i--)
#define mst(abc,bca) memset(abc,bca,sizeof abc)
#define X first
#define Y second
#define lowbit(a) (a&(-a))
#define debug(a) cout<<#a<<":"<<a<<"\n"
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long double ld;
const int N=15;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-6;
const double PI=acos(-1.0);

int n,k,R,ans;
int x[N],y[N],r[N];
vector<int> g;
bool vis[20][20];
set<int> s;

int dis(int x1,int y1,int x2,int y2){
    return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}

int countBit(int num){
    int count=0;
    while(num){
            num=num&(num-1);
         count++;
    }
    return count;
}

void dfs(int i,int cnt,int st){
    if(cnt==k){
        ans=max(ans,countBit(st));
        return;
    }
    if(i==g.size()) return;
    dfs(i+1,cnt+1,st|g[i]);
    dfs(i+1,cnt,st);
}

void solve(){
    cin>>n>>k>>R;
    rep(i,0,n-1) cin>>x[i]>>y[i]>>r[i];
    rep(xx,-7,7) rep(yy,-7,7){
        int st=0;
        rep(i,0,n-1)
            if(dis(xx,yy,x[i],y[i])<=(R+r[i])*(R+r[i])) st|=1<<i;
        s.insert(st);
    }
    for(auto &x:s) g.pb(x);
    dfs(0,0,0);
    cout<<ans<<"\n";
}


int main(){
    ios::sync_with_stdio(0);cin.tie(0);
//    int t;cin>>t;while(t--)
    solve();
    return 0;
}