题目链接

一个搜索,或者状压,蒟蒻不会状压dp,就写了搜索。。。


  • 一个猪,有两种方式死,一是只被一只鸟打死,另外一个是和之前一只猪一起被同一只鸟打死,因为两只猪确定一条抛物线。
  • 然后搜索其实就是对于第i个猪,到目前为止已经确定了ok条抛物线,还有no个没有组成抛物线的猪(就是独自被一只鸟打死的),然后看一下之前已经组成的抛物线有没有一条能够打死该猪,可以的话就往后搜就行,不然就分两种情况:

    1. 这只猪和这只猪之前的一只猪组成一条抛物线。
    2. 这只猪单独被打中。

    对于每种情况单独搜索即可。具体描述放在代码里。

#include<bits/stdc++.h>
using namespace std;

int n, m, ans;
int maxn;
struct node{
    double x, y;
}a[20];
struct node1{
    double a, b;
}p[20];
bool vis[20];

bool sam(double a, double b){
    return abs(a - b) <= 1e-6;
}

void dfs(int k, int ok, int no){
    if(k == n + 1){
        ans = min(ans, ok + no);
    }
    if(ok + no >= ans) return;
    //这个地方一定得注意,上面这句写>=是最优性剪枝。
    //一定得写>=,写>会超时,T一个点。
    //下面一定得>,因为会WA。。。
    if(ok + no > maxn) return;
    int flag = 1;
    for(int i = 1; i <= ok; i++){
        if(sam(p[i].a*a[k].x*a[k].x+p[i].b*a[k].x, a[k].y)){
            //这里处理了第一种情况,就是能和之前已经有的抛物线组成一起。
            //然后vis数组这个比较正常。
            vis[k] = 1;
            dfs(k + 1, ok, no);
            vis[k] = 0;
            flag = 0;
            break;
        }
    }
    if(flag){
        //这里处理第二种情况,与这个猪前面其中一个猪组成一条抛物线。
        for(int i = 1; i < k; i++){
            if(vis[i]) continue;
            if(a[i].x == a[k].x) continue;
            //这里计算一下aa和bb,就是抛物线的a和b,拿方程组手推一下就出来了。
            double aa = (a[k].y*a[i].x/a[k].x-a[i].y)/(a[i].x*(a[k].x-a[i].x));
            double bb = (a[k].y-aa*a[k].x*a[k].x)/a[k].x;
            if(aa < 0){
                p[ok+1].a = aa;
                p[ok+1].b = bb;
                vis[i] = 1;
                vis[k] = 1;
                dfs(k + 1, ok + 1, no - 1);
                vis[i] = 0;
                vis[k] = 0;
            }
        }
        //最后这里是第三种情况,就是这一个单独组成一个抛物线。。。
        dfs(k + 1, ok, no + 1);
    }
}

int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        ans = 0x3f3f3f3f;
        maxn = 0x3f3f3f3f;
        memset(vis, 0, sizeof(vis));
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; i++){
            double x, y;
            scanf("%lf%lf", &x, &y);
            a[i].x = x;
            a[i].y = y;
        }
        if(m == 1) maxn = ceil(n / 3.0 + 1);
        dfs(1, 0, 0);
        printf("%d\n", ans);
    }
    return 0;
}
Last modification:March 14th, 2020 at 08:25 pm