洛谷题单指南-状态压缩动态规划-P2831 [NOIP 2016 提高组] 愤怒的小鸟

原题链接：https://www.luogu.com.cn/problem/P2831

题意解读：求覆盖平面上所有点的最少的曲线数，曲线形如y=ax2+bx

解题思路：

1、两点确定一条曲线

由于曲线方程为：y=ax2+bx，可以判断两点确定一条曲线

设两点为(x1,y1)，(x2,y2)，则有

y1 = ax12 + bx1，y2 = ax22 + bx2

解方程得到：a = (y1/x1-y2/x2)/(x1-x2)，b = y1/x1 - ax1

可以枚举所有两个点构成的曲线，再将所有点代入方程即可确定每条曲线经过了哪些点，每条曲线经过的点可以用状态压缩存入一个整数

设path[i][j]表示第i、j个点构成的曲线经过的所有点的状态

这里有一个特殊情况，如果两个不同的点构成的曲线a不小于0则不合法，如果所有两点构成的曲线都不合法，经过每一个点至少有一个合法的曲线，也

就是path[i][i] = 1 << i，第i个点必有曲线经过i。

2、搜索

dfs(当前已覆盖的点：stat，用了几条曲线：cnt)

{

  if stat表示所有点已覆盖

    ans = min(ans, cnt)

    return

  for 所有当前没有覆盖的点

    对于任意一个没有覆盖的点，找到所有经过它的曲线

      用曲线经过的点的状态 | stat，得到newstat

      继续dfs(newstat, cnt + 1) 

    break，每次只找一个没有覆盖的点，用所有经过它的曲线去更新状态

}

调用：dfs(0, 0)

3、考虑到性能，可以定义f[i]记录已覆盖点状态为i时经过的最少曲线数，使用记忆化搜索

dfs(当前已覆盖的点：stat，用了几条曲线：cnt)

{

  if(f[i] != INF && f[i] <= cnt) return;

  f[i] = min(f[i], cnt)

  if stat表示所有点已覆盖

    ans = min(ans, cnt)

    return

  for 所有当前没有覆盖的点

    对于任意一个没有覆盖的点，找到所有经过它的曲线

      用曲线经过的点的状态 | stat，得到newstat

      继续dfs(newstat, cnt + 1) 

    break，每次只找一个没有覆盖的点，用所有经过它的曲线去更新状态

}

4、注意浮点数的比较不能直接用==，应该相减看是否小于一个更小的值

100分代码：

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

const int N = 18, INF = 0x3f3f3f3f;
const double EPS = 1e-6;
struct Point
{ 
    double x, y; 
} points[N];
int path[N][N]; //path[i][j]表示i，j两个点构成的曲线经过的所有点的状态
int f[1 << N]; //f[i]表示经过的所有点的状态为i时所需的最少曲线数
int t, n, m, ans;

int cmp(double x, double y)
{
    if(fabs(x - y) < EPS) return 0;
    if(x > y) return 1;
    else if(x < y) return -1;
}

void dfs(int stat, int cnt)
{
    if(f[stat] <= cnt) return; //记忆化+最优性剪枝
    f[stat] = min(f[stat], cnt);
    if(stat == (1 << n) - 1) //所有点都已覆盖
    {
        ans = min(ans, cnt);
        return;
    }
    for(int i = 0; i < n; i++)
    {
        if(!(stat >> i & 1))
        {
            for(int j = 0; j < n; j++)
            {
                if(path[i][j])
                {
                    int newstat = stat | path[i][j];
                    dfs(newstat, cnt + 1);
                }
            }
            break; //每次取一个未被覆盖的点，用经过该点的不同曲线去更新覆盖状态
        }
    }
}

int main()
{
    cin >> t;
    while(t--)
    {
        memset(path, 0, sizeof(path));
        cin >> n >> m;
        for(int i = 0; i < n; i++)
        {
            cin >> points[i].x >> points[i].y;
        }
        for(int i = 0; i < n; i++)
        {
            path[i][i] = 1 << i; //每个点一定有一条经过它的曲线
            for(int j = 0; j < n; j++)
            {
                double x1 = points[i].x, y1 = points[i].y;
                double x2 = points[j].x, y2 = points[j].y;
                if(!cmp(x1, x2)) continue; //两点横坐标相同，必然不能形成经过原点的曲线
                double a = (y1 / x1 - y2 / x2) / (x1 - x2);
                double b = y1 / x1 - a * x1;
                if(cmp(a, 0.0) != -1) continue; //a必须小于0
                //找到曲线y=ax^2+bx经过的所有点
                for(int k = 0; k < n; k++)
                {
                    double x = points[k].x, y = points[k].y;
                    if(!cmp(y, a * x * x + b * x))
                    {
                        path[i][j] |= (1 << k);
                    }
                }
            }
        }
        ans = INF;
        memset(f, 0x3f, sizeof(f));
        dfs(0, 0);
        cout << ans << endl;
    }
    return 0;
}