深度优先搜索+暴力枚举

#include <bits/stdc++.h> using namespace std; //空调的结构体 struct Airt{ int a; int b; int p; int m; }; //空调的数组 Airt a[11]; //牛栏数组 int f[105]; //N=牛的数量，M=空调数量，minn=最小的花费 int N,M,minn=100010; //检查v存储的空调方案是否能满足条件 void check(vector<int> v){ int tmp[105],cnt=0; memcpy(tmp,f,sizeof(f)); for(int i=0;i<M;i++){ if(v[i]==1){ for(int j=a[i+1].a;j<=a[i+1].b;j++){ tmp[j]-=a[i+1].p; } cnt+=a[i+1].m; } } for(int i=1;i<=100;i++){ if(tmp[i]>0)return; } minn=min(minn,cnt); } //用递归生成空调的方案 //当递归到0时说明已经添加了所有的方案，可以把方案提交给check void dfs(int x,vector<int> v){ if(!x){ check(v); return ; } vector<int> v1,v2; v1=v2=v; v1.push_back(1); v2.push_back(0); dfs(x-1,v1); dfs(x-1,v2); return ; } int main(){ cin >> N >> M; for(int i=1;i<=N;i++){ int s,t,c; cin >> s >> t >> c; for(int j=s;j<=t;j++){ f[j]=c; } } for(int i=1;i<=M;i++){ cin >> a[i].a >> a[i].b >> a[i].p >> a[i].m; } vector<int> v(0); dfs(M,v); // cout << minn; return 0; }

注意奶牛范围不重叠，可以用桶存。

#include <iostream> #include <cstring> using namespace std; int t[105],vis[10],a[15],b[15],c[15],d[15],ans=1e9; int st[105]; int n,m; void dfs(int u,int sum){ if(u==m+1){ memset(st,0,sizeof st); for(int i=1;i<=m;i++){ if(vis[i]){ for(int j=a[i];j<=b[i];j++){ st[j]+=c[i]; } } } for(int i=0;i<=100;i++){ if(st[i]<t[i]){ return ; } } ans=min(ans,sum); return ; } vis[u]=1; dfs(u+1,sum+d[u]); vis[u]=0; dfs(u+1,sum); } int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ int a,b,c; cin>>a>>b>>c; for(int j=a;j<=b;j++){ t[j]+=c; } } for(int i=1;i<=m;i++){ cin>>a[i]>>b[i]>>c[i]>>d[i]; } dfs(1,0); cout<<ans; return 0; }