自动搬运

查看原文

来自洛谷，原作者为

	Jorisy 之所以能够离去而义无反顾 / 仅因我记得你已厌倦的梦 / 连最后的道别都稀薄的风中 / 用加倍的叛逆做出抗争

搬运于2025-08-24 22:44:33，当前版本为作者最后更新于2023-02-04 18:30:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

数据范围较小，易想到 dfs 暴力搜索。

首先对于输入的 $s_i,t_i,c_i$，我们开一个桶 $cw$，将对于 $s_i\le\forall j\le t_i$，执行 $cw_j\leftarrow cw_j+c_i$。

然后开始 dfs。

dfs 每次做选或不选，在第 $dep$ 层选就是对于 $a_{dep}\le\forall i\le b_{dep}$，执行 $cw_i\leftarrow cw_i-p_{dep}$，然后价值 $+m_{dep}$。注意回溯。

然后搜完验证是否对于 $1\le\forall i\le \max\{t_i\}$，满足 $cw_i\le 0$ 即可。

赛时 AC Code：

#include<bits/stdc++.h>
using namespace std;

int n,m,k,ans=1e9,cw[105],s[25],t[25],c[25],a[25],b[25],p[25],v[25];

bool f()//是否满足
{
	for(int i=1;i<=k;i++)
	{
		if(cw[i]>0) return 0;
	}
	return 1;
}

void dfs(int dep,int s)
{
	if(dep>m)
	{
		//cerr<<"DE: ";for(int i=1;i<=k;i++) cerr<<cw[i]<<' ';cerr<<endl;
		if(f()) ans=min(ans,s);//合法就更新答案
		return;
	}
	dfs(dep+1,s);//不选
	for(int i=a[dep];i<=b[dep];i++) cw[i]-=p[dep];
	dfs(dep+1,s+v[dep]);//选
	for(int i=a[dep];i<=b[dep];i++) cw[i]+=p[dep];//回溯
}

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>s[i]>>t[i]>>c[i];
		k=max(k,t[i]);
		for(int j=s[i];j<=t[i];j++) cw[j]+=c[i];//事先处理
	}
	for(int i=1;i<=m;i++) cin>>a[i]>>b[i]>>p[i]>>v[i];
	dfs(1,0);
	cout<<ans;
	return 0;
}