前置芝士:枚举子集
是的,我们分为取和不取的情况考虑然后取最小值就行了。
这里用二进制模拟,其实很多方法都可以实现。
可以先把每个单位的牛棚所要的温度加上,如果最后减的话每个单位都比 0 小,那么我们就取最小值。
由于 $m$ 的范围非常小,所以是可以过去的。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],f[N],x[N],n,m;
struct node{
int l,r,x,t;
}s[N];
string bin(int n,int m)
{
int x[101],t=0,s=m;
while(n!=0){
x[t]=n%2;
t++;
n=n/2;
}
string st="";
while(t<s){
s--;
st+='0';
}
for(int i=t-1;i>=0;i--)st+=char(x[i]+48);
return st;
}
int main()
{
cin>>n>>m;
int L=INT_MAX,R=0;
for(int i=1;i<=n;i++){
int l,r,c;
cin>>l>>r>>c;
a[l]+=c;
a[r+1]-=c;
L=min(L,l);//左边界
R=max(R,r);//有边界
}
//多余的区域是不需要管的。
for(int i=L;i<=R;i++)f[i]=f[i-1]+a[i];//差分求每一的单位所需减少的温度。
//for(int i=L;i<=R;i++)cout<<f[i]<<' ';
for(int i=1;i<=m;i++)cin>>s[i].l>>s[i].r>>s[i].x>>s[i].t;
int mi=INT_MAX;
for(int i=0;i<=pow(2,m)-1;i++){
for(int j=L;j<=R;j++)x[j]=f[j];
string st=bin(i,m);
int ans=0;
for(int j=0;j<st.size();j++){
if(st[j]=='1'){
for(int k=s[j+1].l;k<=s[j+1].r;k++)x[k]-=s[j+1].x;
ans+=s[j+1].t;
}
}
bool ok=1;
//for(int j=L;j<=R;j++)cout<<x[j]<<' ';
//puts("");
for(int j=L;j<=R;j++)
if(x[j]>0){
ok=0;
break;
}
if(ok)mi=min(mi,ans);
}
cout<<mi;
}