题目描述

简单来说就是给你N头奶牛，M个空调，你需要确保满足每一头奶牛在区间[s - t]降温c度的要求， 每个空调的降温区间为[a - b]，可以降温p度，花费是m。求所有花费的最小值

数据量很小直接暴搜，遍历每一个空调，每一个空调都有两种状态选或者不选，所以他的可能是是2^10 不会超时

自认码风不错， 代码内容就很清晰了

C++ 代码

#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int n, m;
int b[105];
int ans = 2e9, mx;

struct cow
{
    int s, t, c;
}a[25];

struct Ac
{
    int a, b, p, c;
}ac[15];

void dfs(int u, int num)
{
    if (u > m)
    {
        for (int i = 1 ; i <= mx ; i ++ )
            if (b[i] > 0) return;

        ans = min(ans, num); // 如果全部牛棚小于0 说明温度已经全部符合要求了 把这个合法的方案更新一下
        return;
    }


    dfs(u + 1, num); // 不选择使用这个空调

    for (int j = ac[u].a ; j <= ac[u].b ; j ++ ) b[j] -= ac[u].p;

    dfs(u + 1, num + ac[u].c); // 选择使用这个空调

    for (int j = ac[u].a ; j <= ac[u].b ; j ++ ) b[j] += ac[u].p;

}

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

    for (int i = 1 ; i <= n ; i ++ )
    {
        scanf("%d%d%d", &a[i].s, &a[i].t, &a[i].c); //读入牛的左右端点以及他要求的下降的温度
        for (int j = a[i].s ; j <= a[i].t ; j ++ ) b[j] = a[i].c;
        mx = max(mx, a[i].t); // 更新有牛的牛棚最右端的端点
    }
    for (int i = 1 ; i <= m ; i ++ ) scanf("%d%d%d%d", &ac[i].a, &ac[i].b, &ac[i].p, &ac[i].c); // 读入空调的左右端点，费用以及能够降低的温度

    dfs(1,0);

    printf("%d", ans);

    return 0;
}