Loading... [题目链接](https://www.luogu.org/problem/P2831) 一个搜索，或者状压，蒟蒻不会状压dp，就写了搜索。。。 <!--more--> --- - 一个猪，有两种方式死，一是只被一只鸟打死，另外一个是和之前一只猪一起被同一只鸟打死，因为两只猪确定一条抛物线。 - 然后搜索其实就是对于第i个猪，到目前为止已经确定了ok条抛物线，还有no个没有组成抛物线的猪（就是独自被一只鸟打死的），然后看一下之前已经组成的抛物线有没有一条能够打死该猪，可以的话就往后搜就行，不然就分两种情况： 1. 这只猪和这只猪之前的一只猪组成一条抛物线。 2. 这只猪单独被打中。 对于每种情况单独搜索即可。具体描述放在代码里。 ```cpp #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 14, 2020 © Allow specification reprint Like 如果觉得我的文章对你有用，请随意赞赏