AcWing 4889. 空调II
考虑到空调的数量M<= 10,可以使用暴力枚举的方法,暴力枚举每个空调可以使用二进制枚举的方式来简化,用1/0来表示这个空调开/不开 ,然后枚举每一个牛的牛栏是否达到降温需求,若达到,就和答案取min
int n,m;
struct Cow
{
LL s,t,c;
}cows[N];
struct Ac
{
LL a,b,p,m;
}acs[N];
int w[N];
void solve()
{
cin >> n >> m;
for (int i = 0;i < n;i ++)
{
int s,t,c; cin >> s >> t >> c;
cows[i] = {s,t,c};
}
for (int i = 0;i < m;i ++)
{
int a,b,p,m; cin >> a >> b >> p >> m;
acs[i] = {a,b,p,m};
}
LL ans = inf;
for (int i = 0;i < 1 << m;i ++)
{
memset(w,0,sizeof w);//每次将牛栏的降温情况清空
LL cost = 0;
for (int j = 0;j < m;j ++)//枚举每个空调开不开
if (i >> j & 1)
{
int a = acs[j].a,b = acs[j].b,p = acs[j].p,m = acs[j].m;
cost += m;
for (int k = a;k <= b;k ++)
w[k] += p;//降温
}
bool f = true;
for (int i = 0;i < n;i ++)
{
int s = cows[i].s,t = cows[i].t,c = cows[i].c;
for (int j = s;j <= t;j ++)
if (w[j] < c)
{
f = false;
break;
}
}
if (f) ans = min(ans,cost);
}
cout << ans << endl;
}