题解：P12282 [蓝桥杯 2024 国 Python A] 羊圈
ylch
·
·
题解
发现 n 和 m 都很小，尤其是 n 最大只有 15，暴力自然是可以枚举栅栏的全排列，然后 01dfs 每个位置是否放栅栏。
数据范围小，且可以转化为全排列问题，所以考虑状压 dp。
根据暴力，我们需要知道当前栅栏的使用情况和当前位置（确定放栅栏后能框住的范围），所以设 f_{i,S} 表示当前位置为 i，栅栏使用状态为 S 时，跑掉的羊的数量的最小期望。
想了一会转移方程，发现直接求最小逃跑期望不大好求，考虑正难则反，设 f_{i,S} 表示最大不逃跑期望。
转移方程：
答案即为所有的 $\min\{\sum\limits_{k=1}^{n} p_k-f_{m,S}\}$。
注意特判如果所有羊圈能完全覆盖所有羊，则直接输出 $0$。
```cpp
#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;
}
```