2019牛客暑期NOIP真题班提高组10-DP3

1. 愤怒的小鸟

来源：NOIP2016提高组 https://ac.nowcoder.com/acm/contest/264/C

算法知识点: 状态压缩DP

复杂度：

解题思路：

一般抛物线方程：

题目中的抛物线有两个特点：

1. 过原点, 即
2. 开口向下，即

因此抛物线方程为：，有两个未知数，因此两点即可确定一条抛物线。

因此最多有 个不同的抛物线。接下来求出所有不同的抛物线，及其能覆盖的所有点的点集。

此时问题变成了经典的“重复覆盖问题”，即给定01矩阵，要求选择尽量少的行，将所有列覆盖住。

f[i] 表示当前已经覆盖的列是i时的最小行数。

转移时随便找到当前未被覆盖的某一列 ，然后枚举所有包含 的行j来选择即可。

即：f[i | j] = min(f[i | j], f[i] + 1)。

C++ 代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

#define x first
#define y second

using namespace std;

typedef pair<double, double> PDD;

const int N = 18, M = 1 << N;
const double eps = 1e-6;

int n, m;
PDD q[N];
int path[N][N];
int f[M];
int ulowbit[M];

int cmp(double x, double y)
{
    if (fabs(x - y) <= eps) return 0;
    if (x < y) return -1;
    return 1;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; i ++ ) scanf("%lf%lf", &q[i].x, &q[i].y);

        for (int i = 0; i + 1 < 1 << n; i ++ )
        {
            for (int j = 0; j < n; j ++ )
                if (!(i >> j & 1))
                {
                    ulowbit[i] = j;
                    break;
                }
        }

        memset(path, 0, sizeof path);

        for (int i = 0; i < n; i ++ )
        {
            path[i][i] = 1 << i;
            for (int j = 0; j < n; j ++ )
            {
                if (!cmp(q[i].x, q[j].x)) continue;
                double x1 = q[i].x, y1 = q[i].y, x2 = q[j].x, y2 = q[j].y;
                double b = (y1 * x2 * x2 / x1 / x1 - y2) / (x2 * x2 / x1 - x2);
                double a = (y1 - b * x1) / x1 / x1;
                if (a > 0) continue;
                int state = 0;
                for (int k = 0; k < n; k ++ )
                {
                    double x = q[k].x, y = q[k].y;
                    if (!cmp(y, a * x * x + b * x)) state += 1 << k;
                }

                path[i][j] = state;
            }
        }

        memset(f, 0x3f, sizeof f);
        f[0] = 0;

        for (int i = 0; i + 1 < 1 << n; i ++ )
        {
            int x = ulowbit[i];
            for (int j = 0; j < n; j ++ )
                f[i | path[x][j]] = min(f[i | path[x][j]], f[i] + 1);
        }

        printf("%d\n", f[(1 << n) - 1]);
    }

    return 0;
}

2. 换教室

来源：NOIP2016提高组 https://ac.nowcoder.com/acm/contest/264/F

算法知识点: 数学期望,动态规划

复杂度：

解题思路：

状态表示：

• f[i][j][0]表示前i个课程，申请换了j次，且最后一次没申请换的最小期望长度
• f[i][j][1]表示前i个课程，申请换了j次，且最后一次申请交换的最小期望长度

则f[i][j][0]在如下两种情况中取最小值即可：

• 第i - 1个课程没申请交换，最小期望是f[i - 1][j][0] + d[a[i - 1]][a[i]]
• 第i - 1个课程申请交换，最小期望是f[i - 1][j][0] + d[a[i - 1]][a[i]] * (1 - p[i - 1]) + d[b[i - 1]][a[i]] * p[i - 1]

f[i][j][1]可以用类似的方式得到。

最后遍历f[n][j][k]取最小值就是答案。

C++ 代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 2010, M = 310;
const double INF = 1e9;

int n, m, V, E;
int a[N], b[N];
double p[N];
int d[M][M];
double f[N][N][2];

int main()
{
    scanf("%d%d%d%d", &n, &m, &V, &E);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &b[i]);
    for (int i = 1; i <= n; i ++ ) scanf("%lf", &p[i]);

    memset(d, 0x3f, sizeof d);
    for (int i = 1; i <= V; i ++ ) d[i][i] = d[0][i] = 0;

    for (int i = 0; i < E; i ++ )
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        d[u][v] = d[v][u] = min(d[u][v], w);
    }

    for (int k = 1; k <= V; k ++ )
        for (int i = 1; i <= V; i ++ )
            for (int j = 1; j <= V; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

    for (int i = 0; i <= n; i ++ )
        for (int j = 0; j <= m; j ++ )
            for (int k = 0; k <= 1; k ++ )
                f[i][j][k] = INF;

    f[1][0][0] = f[1][1][1] = 0;
    for (int i = 2; i <= n; i ++ )
    {
        for (int j = 0; j <= m; j ++ )
        {
            f[i][j][0] = min(f[i - 1][j][0] + d[a[i - 1]][a[i]], 
                             f[i - 1][j][1] + d[a[i - 1]][a[i]] * (1 - p[i - 1]) + d[b[i - 1]][a[i]] * p[i - 1]);
            if (j)
                f[i][j][1] = min(f[i - 1][j - 1][0] + d[a[i - 1]][a[i]] * (1 - p[i]) + d[a[i - 1]][b[i]] * p[i],
                                 f[i - 1][j - 1][1] + d[a[i - 1]][a[i]] * (1 - p[i - 1]) * (1 - p[i])
                                                    + d[b[i - 1]][a[i]] * p[i - 1] * (1 - p[i])
                                                    + d[a[i - 1]][b[i]] * (1 - p[i - 1]) * p[i]
                                                    + d[b[i - 1]][b[i]] * p[i - 1] * p[i]);
        }
    }

    double res = INF;
    for (int i = 0; i <= m; i ++ ) res = min(res, min(f[n][i][0], f[n][i][1]));

    printf("%.2lf\n", res);
    return 0;
}

3. 宝藏

来源：NOIP2017提高组 https://ac.nowcoder.com/acm/contest/265/B

算法知识点: 状态压缩DP

复杂度：

解题思路：

参考这篇题解所写。

状态压缩DP，下文中i是一个 位二进制数，表示每个点是否存在。

状态f[i][j]表示：

• 集合：所有包含i中所有点，且树的高度等于j的生成树
• 属性：最小花费

状态计算：枚举i的所有非全集子集S作为前j - 1层的点，剩余点作为第j层的点。
核心： 求出第j层的所有点到S的最短边，将这些边权和乘以j，直接加到f[S][j - 1]上，即可求出f[i][j]。

证明：
将这样求出的结果记为f'[i][j]

• f[i][j]中花费最小的生成树一定可以被枚举到，因此f[i][j] >= f'[i][j]；
• 如果第j层中用到的某条边(a, b)应该在比j小的层，假设a是S中的点，b是第j层的点，则在枚举S + {b}时会得到更小的花费，即这种方式枚举到的所有花费均大于等于某个合法生成树的花费，因此f[i][j] <= f'[i][j]

所以有 f[i][j] = f'[i][j]。

C++ 代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 12, M = 1 << 12, INF = 0x3f3f3f3f;

int n, m;
int d[N][N];
int f[M][N], g[M];

int main()
{
    scanf("%d%d", &n, &m);

    memset(d, 0x3f, sizeof d);
    for (int i = 0; i < n; i ++ ) d[i][i] = 0;

    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        a --, b --;
        d[a][b] = d[b][a] = min(d[a][b], c);
    }

    for (int i = 1; i < 1 << n; i ++ )
        for (int j = 0; j < n; j ++ )
            if (i >> j & 1)
            {
                for (int k = 0; k < n; k ++ )
                    if (d[j][k] != INF)
                        g[i] |= 1 << k;
            }

    memset(f, 0x3f, sizeof f);
    for (int i = 0; i < n; i ++ ) f[1 << i][0] = 0;

    for (int i = 1; i < 1 << n; i ++ )
        for (int j = (i - 1); j; j = (j - 1) & i)
            if ((g[j] & i) == i)
            {
                int remain = i ^ j;
                int cost = 0;
                for (int k = 0; k < n; k ++ )
                    if (remain >> k & 1)
                    {
                        int t = INF;
                        for (int u = 0; u < n; u ++ )
                            if (j >> u & 1)
                                t = min(t, d[k][u]);
                        cost += t;
                    }

                for (int k = 1; k < n; k ++ ) f[i][k] = min(f[i][k], f[j][k - 1] + cost * k);
            }

    int res = INF;
    for (int i = 0; i < n; i ++ ) res = min(res, f[(1 << n) - 1][i]);

    printf("%d\n", res);
    return 0;
}