NKOJ 3751 扫雷的游戏

问题描述

有一款有趣的手机游戏。棋盘上有n颗地雷，玩家需要至少扫掉其中的k颗雷。
每一步，玩家可以用手指在手机屏幕上划一条直线，该直线经过的地雷都会被扫除掉。
问，最少需要划几次就能扫除k颗以上的地雷？

输入格式

有两组测试数据，对于每组数据：
第一行，一个整数n，表示地雷的总数
第二含，一个整数k，表示至少需要扫掉的雷数
接下来n行，每行两个整数x和y，表示一颗地雷的坐标。

输出格式

两行，每行一个整数，表示对应数据的答案

样例输入

4
4
1 1
1 2
2 1
2 2
9
7
1 1
2 2
1 3
3 1
3 3
4 1
4 2
4 3
4 5

样例输出

2
2

#include <stdio.h>
#include <bits/stdc++.h>
#define inf 999999999
using namespace std;
int n, m;
int dp[65540];//dp[s]表示在状态为s的前提下，达到目标状态最少需要线段个数 
int Line[20][20];
struct nodgd{int x; int y;}p[20];
bool orz(int i, int j, int k){
    return ((p[i].x-p[j].x)*(p[i].y-p[k].y)==(p[i].y-p[j].y)*(p[i].x-p[k].x));
}
int dfs_dp(int s){
    if(dp[s] != inf)return dp[s];
    int i, j, cnt = 0;//cnt为剩余点的个数 
    for(i = 0; i < n; i ++)if(s & (1 << i))cnt ++;
    if(n - m >= cnt)return dp[s] = 0;
    if(cnt == 1)return dp[s] = 1;//特判！！！！！！！
    for(i = 1; i <= n; i ++) 
        if(s & (1 << i - 1)){//如果s里面有i这个点
            for(j = i + 1; j <= n; j ++)
                if(s & (1<<j-1))dp[s] = min(dp[s],dfs_dp(s&(~Line[i][j])) + 1);
        }
    return dp[s];
}
int main(){
    int t = 2;
    while(t --){
        cin>>n>>m;
        for(int i = 1; i <= n; i ++)cin>>p[i].x>>p[i].y;
        for(int i = 1; i <= n; i ++)//为哈要从i=0开始啊 
            for(int j = 1; j <= n; j ++){
                if(i == j)continue;
                for(int k = 1; k <= n; k ++)
                    if(orz(i, j, k))Line[i][j] = Line[i][j]|(1 << k-1);
            }
        for(int s = 0; s <= (1 << n) - 1; s ++)dp[s] = inf;
        cout<<dfs_dp((1 << n) - 1)<<endl;
        if(t == 1){
            memset(Line, 0, sizeof(Line));
            memset(p, 0, sizeof(p));
        }
    }
}

NKOJ 3751 扫雷的游戏

原文：https://www.cnblogs.com/qwqq/p/11066194.html