Air Cownditioning (USACO Bronze 2023 January)

$N=20$ 头牛，每头占据连续的一段牛栏，需要降低一定的温度，有 $M=10$ 台空调，每台能降低另外一个区间的牛栏的温度若干，价格也不同。问怎样满足牛的温度要求，而且最便宜。

虽然要求比较多，但是我们看到重要条件是牛的数量和空调的数量都很少。所以应该想一下暴力搜索是否可行。一共10台空调，每台有开关两种状态，所以整个状态空间的大小就是 $2^{10}$ ，也就是1024，而验证一个状态是否可行和花费如何，复杂度是 $\mathcal{O}(N+M)$ ，所以整体复杂度还是很低，暴力搜索可行。

记得我们可以用这样的循环来生成所有打开空调的组合：

for (int i = 1; i < (1<<M); i++) {
    for (int j = 0; j < M; j++) {
        if (i & (1<<j)) {
            // 第j个空调开的情况
        }
    }
}

完整程序：

#include <cstdio>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
 
int n, M;
int s[25], t[25], c[25];
int a[15], b[15], p[15], m[15];
int P[105];        // temp reduce per stall
 
int main() {
    scanf("%d %d", &n, &M);
    for (int i = 0; i < n; i++)
        scanf("%d %d %d", &s[i], &t[i], &c[i]);
    for (int i = 0; i < M; i++)
        scanf("%d %d %d %d", &a[i], &b[i], &p[i], &m[i]);
    
    int ans = 1e9;
    for (int i = 1; i < (1<<M); i++) {
        fill(P, P+101, 0);
        int cost = 0;
        for (int j = 0; j < M; j++) {
            if (i & (1<<j)) {
                for (int k = a[j]; k <= b[j]; k++)
                    P[k] += p[j];
                cost += m[j];
            }
        }
        bool ok = true;
        for (int j = 0; j < n; j++)
            for (int k = s[j]; k <= t[j]; k++)
                if (P[k] < c[j])
                    ok = false;
        if (ok)
            ans = min(ans, cost);
    }
    printf("%d", ans);
 
    return 0;
}