思路
- 先把所有点为圆心的攻击范围能够消灭敌人的情况用二进制存下来(状态压缩,消灭用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;
}