题解 | 小红的显存清理挑战

写一个搜索加剪纸的做法

首先这是一个比较典型的背包DP

所以可以考虑有搜索来做，第一步是预处理，两种成本无脑选成本低的

再进一步预处理，把成本和空间做除法，形成每一个要不要考虑拿的性价比信息

在排序把性价比高的放在前面，优先拿高性价比的

后面就可以开始搜索了，考虑三个状态信息，其一，目前搜到第几层了，其二，已经释放多少空间了，其三，花费了多少成本

搜索过程中可以加一点剪纸优化，比如说如果我已经搜到结果了，如果新搜的状态成本比我高，空间还比我少，我就没必要继续搜下去了，之间return

代码思路比较简单如下了

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

int n,m;
int mem[100005];
int cost1[100005],cost2[100005];
int tot;
int cst[100005];
struct node{
	int mem,cost1,cost2,cst;
	double xjb;
};
node a[100005];

bool cmp(node t1,node t2){return t1.xjb>t2.xjb;}
int ans=1000000007;
void dfs(int pos,int sz,int CST)
{
	if(pos==n+1)return;
	if(sz>=m)
	{
		ans=min(ans,CST);
		return;
	}
	if(CST>ans&&sz<m)return;
	dfs(pos+1,sz+a[pos].mem,CST+a[pos].cst);
	dfs(pos+1,sz,CST);
}

int main()
{
	cin>>m>>n;
	for(int i=1;i<=n;i++)
	{
			cin>>a[i].mem;
		tot+=a[i].mem;
	}
	for(int i=1;i<=n;i++)
		cin>>a[i].cost1;
	for(int i=1;i<=n;i++)
		cin>>a[i].cost2;
	if(tot<m)
	{
		cout<<"error";
		return 0;
	}
	for(int i=1;i<=n;i++)
	{
		a[i].cst=min(a[i].cost1,a[i].cost2);
		a[i].xjb=double(a[i].mem)/double(a[i].cst);
	}
	sort(a+1,a+n+1,cmp);
	dfs(1,0,0);//DFS(考虑到了第几个张量，当前释放了多少空间，花费的成本有多少)
	cout<<ans;
}