P9011 [USACO23JAN] Air Cownditioning II B

题目描述

农夫约翰的 $N$ 头奶牛 $(1≤N≤20)$ 住在一个谷仓里，谷仓里有连续的牛栏，编号为 $1-100$ 。 奶牛 $i$ 占据了编号 $[s_i,t_i]$ 的牛栏。 不同奶牛占据的牛栏范围是互不相交的。 奶牛有不同的冷却要求，奶牛 $i$ 占用的每个牛栏的温度必须至少降低 $c_i$ 单位。

谷仓包含 $M$ 台空调，标记为 $1-M$ $(1\le M\le10)$。第 $i$ 台空调需要花费 $m_i$ 单位的金钱来运行 $(1\le m_i \le 1000)$ ，如果运行，第 $i$ 台空调将牛栏 $[a_i,b_i]$ 所有牛栏的温度降低 $p_i$（$1\le p_i\le10^6）$。 空调覆盖的牛栏范围可能会重叠。

请帮助农夫约翰求出满足所有奶牛需求要花费的最少金钱。

输入格式

第一行两个整数，分别为 $N$ 和 $M$。

第 $2$ 至 $(N+1)$ 行，每行三个整数，分别为 $s_i$、$t_i$ 和 $c_i$ 。

第 $(N+2)$ 至 $(M+N+1)$ 行，每行四个整数， 分别为 $a_i$、$b_i$、$p_i$ 和 $m_i$。

输出格式

一个整数，表示最少花费的金钱。

输入输出样例 #1

输入 #1

2 4
1 5 2
7 9 3
2 9 2 3
1 6 2 8
1 2 4 2
6 9 1 5

输出 #1

10

说明/提示

样例解释 1

一种花费最少的可能解决方案是选择那些冷却区间为 $[2,9]$ 、$[1,2]$ 和 $[6,9]$ 的空调，成本为 $3+2+5=10$ .

对于 $100\%$ 的数据，$1 \le N \le 20$， $1 \le M \le 10$, $1 \le a_i, b_i, s_i, t_i \le 100$, $1 \le c_i, p_i \le 10^6$， $1 \le m_i \le 1000$。

正解

#include<bits/stdc++.h>
using namespace std;
struct nl{
	int niu;
	int jw;
}nl1[110];
struct kt{
	int a;
	int b;
	int p;
	int m;
} kt1[15];
int n,m,kt_jw[110],fy_sum,ans=1e9,rr_nl=0,ll_nl=100;
int flag[15];

bool judge(){
	// 求每个牛栏的空调降温效果和花钱总和
	memset(kt_jw,0,sizeof(kt_jw));
	fy_sum=0;
	for(int i=1;i<=m;i++){
//		cout<<flag[i]<<" ";
		if(flag[i]){
			fy_sum+=kt1[i].m;
			for(int j=kt1[i].a;j<=kt1[i].b;j++){
				kt_jw[j]+=kt1[i].p;
			}
		}
	}
//	cout<<" "<<fy_sum<<endl;
//	 比较每个牛栏的温度是否达到降温需求
	for(int i=ll_nl;i<=rr_nl;i++){
		
		if(nl1[i].jw>kt_jw[i]){
//			cout<<i<<"号牛栏比较"<<nl1[i].jw<<" "<<kt_jw[i]<<endl;
			return false;
		}
	}
//	cout<<"yes"<<fy_sum<<endl;
	return true;
}


void dfs(int x){//请判断第x台空调是否使用
	// 递归边界条件
	if(x>m){
		// 设置完m空调的状态，此时要判断此时的状态是否满足题目要求
		if(judge()){
			//符合判断要求，就擂台法比大小
			ans=min(ans,fy_sum);
		}
		return;
	}
	flag[x]=0;
	dfs(x+1);
	flag[x]=1;
	dfs(x+1);
	return;
}

int main(){
	//输入数据和初始化
	cin>>n>>m;
	for(int i=1;i<=n;i++){//保持牛栏和牛的相关数据到nl1
		int s,t,c;
		cin>>s>>t>>c;
		for(int j=s;j<=t;j++){
			nl1[j].niu=i;
			nl1[j].jw=max(c,nl1[j].jw);
		}
		ll_nl=min(ll_nl,s);
		rr_nl=max(rr_nl,t);
	}
	for(int i=1;i<=m;i++){//保存空调数据到kt1
		cin>>kt1[i].a>>kt1[i].b>>kt1[i].p>>kt1[i].m;
	}
	dfs(1);
	cout<<ans;
	return 0;
}

// dfs选数 路径选择法 排列路径
#include<bits/stdc++.h>
using namespace std;
int a[10];//可以备选的数字
int b[10];//用来标记第几个数字是否已经被选择
int c[10];//用来记录到的数字
int n,m;

void dfs(int x){// 选到了几个数
	// 边界
	if(x>m){//已经选够了
		for(int i=1;i<=m;i++){
			cout<<c[i]<<" ";
		}
		cout<<endl;
		return ;
	}
	// 没选够
	for(int i=1;i<=n;i++){
		if(b[i]==0){
			c[x]=a[i];
			b[i]=1;
			dfs(x+1);
			b[i]=0;
		}
	}		
	return;
	
}

int main(){
	n=9;
	m=3;
	for(int i=1;i<=n;i++){
		a[i] = i;
	}
	
	dfs(1);
	return 0;
}

// dfs选数 路径选择法 组合路径
#include<bits/stdc++.h>
using namespace std;
int a[10];//可以备选的数字
int b[10];//用来标记第几个数字是否已经被选择
int c[10];//用来记录到的数字
int n,m;

void dfs(int x){// 选到了几个数
	// 边界
	if(x>m){//已经选够了
		for(int i=1;i<=m;i++){
			cout<<a[c[i]]<<" ";
		}
		cout<<endl;
		return ;
	}
	// 没选够
	for(int i=c[x-1]+1;i<=n;i++){
		if(b[i]==0){
			c[x]=i;
			b[i]=1;
			dfs(x+1);
			b[i]=0;
		}
	}		
	return;
	
}

int main(){
	n=9;
	m=3;
	for(int i=1;i<=n;i++){
		a[i] = 1000+i;
	}
	
	dfs(1);
	return 0;
}

// dfs选数 01选择法
#include<bits/stdc++.h>
using namespace std;
int a[10];//可以备选的数字
int b[10];//用来标记第几个数字是否已经被选择
int c[10];//用来记录到的数字
int n,m;

void dfs(int x,int t){// x代表第x个数选不选，t代表选到第几个数
	// 边界	
	if(x>n){
		for(int i=1;i<=n;i++){
			cout<<b[i]<<" ";
		}
		cout<<endl;

		return;
	}
	// 选第x个数
	b[x]=1;
	c[t]=a[x];
	dfs(x+1,t+1);
	b[x]=0;
	
	// 不选第x个数
	b[x]=0;
	dfs(x+1,t);
			
	return;
	
}

int main(){
	n=4;
	m=5;
	for(int i=1;i<=n;i++){
		a[i] = i;
//		cout<<a[i]<<" ";
	}
	dfs(1,1);
	return 0;
}