自动搬运

查看原文

来自洛谷，原作者为

	ylch 博观而约取，厚积而薄发 加油！（查看.com域名帖子中的内容，把后缀改成.me即可）

搬运于2025-08-24 23:14:18，当前版本为作者最后更新于2025-06-08 23:20:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

发现 $n$ 和 $m$ 都很小，尤其是 $n$ 最大只有 $15$，暴力自然是可以枚举栅栏的全排列，然后 01dfs 每个位置是否放栅栏。

数据范围小，且可以转化为全排列问题，所以考虑状压 dp。

根据暴力，我们需要知道当前栅栏的使用情况和当前位置（确定放栅栏后能框住的范围），所以设 $f_{i,S}$ 表示当前位置为 $i$，栅栏使用状态为 $S$ 时，跑掉的羊的数量的最小期望。

想了一会转移方程，发现直接求最小逃跑期望不大好求，考虑正难则反，设 $f_{i,S}$ 表示最大不逃跑期望。

转移方程： $f_{i,S}=\max\{f_{i-1,S},\ f_{i-l_j+1,S \setminus j}+\sum\limits_{k=i-l_j+1}^{i} p_k\}$，其中 $i-l_j+1 > 0$。

答案即为所有的 $\min\{\sum\limits_{k=1}^{n} p_k-f_{m,S}\}$。

注意特判如果所有羊圈能完全覆盖所有羊，则直接输出 $0$。

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

int l[15], tot;
double p[205];
double dp[205][1 << 15], sum[205];

int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> l[i], tot += l[i];
    for(int i = 1; i <= m; i ++) cin >> p[i];

    if(tot >= m){ // 特判
        cout << "0.00"; return 0;
    }

    // 前缀和
    for(int i = 1; i <= m; i ++){
        sum[i] = sum[i - 1] + p[i];
    }

    // 初始化dp
    for(int i = 0; i <= m; i ++){
        for(int s = 0; s <(1 << n); s ++){
            dp[i][s] = -1e18;
        }
    }
    dp[0][0] = 0;

    for(int i = 1; i <= m; i ++){
        for(int s = 0; s < (1 << n); s ++){
            // 情况1：当前位置不放任何羊圈
            dp[i][s] = dp[i - 1][s];

            // 情况2：尝试在当前位置放置一个羊圈
            for(int j = 1; j <= n; j ++){
                if((s & (1 << j-1)) && i >= l[j]){
                    dp[i][s] = max(dp[i][s], dp[i - l[j]][s ^ (1 << j-1)] + sum[i] - sum[i - l[j]]);
                }
            }
        }
    }

    double minn = 1e18;
    for(int s = 0; s < (1 << n); s ++){
        minn = min(minn, sum[m] - dp[m][s]);
    }
    if(minn < 1e-8) minn = 0; // 避免精度误差

    cout << fixed << setprecision(2) << minn;
    return 0;
}