49爆搜求助
查看原帖
49爆搜求助
958865
aldzsfs楼主2023/10/5 08:50

全是Wa,没有T

#include<bits/stdc++.h>
using namespace std;
int b,s,ans=INT_MAX,c[10],k[10],p[10],J[200],P[200],x[200][10],y[200][10];
map<int,int>m;
void dfs(int f[],int h){
	if(h>=ans)	return;
	int hd=h;
	for(int i=1;i<=b;++i)	hd+=(k[i]-f[i])*p[i];
	if(hd>=ans)	return;
	ans=hd;
	int fd[10];
	for(int i=1;i<=s;++i){
		for(int i=1;i<=b;++i)	fd[i]=f[i];
		for(int j=1;j<=J[i];++j){
			int t=m[x[i][j]],d=y[i][j];
			if(fd[t]+d>k[t])	goto nxt;
		}
		for(int j=1;j<=J[i];++j)	fd[m[x[i][j]]]+=y[i][j];
		dfs(fd,h+P[i]);
		nxt:;
	}
}
int main(){
	cin>>s;
	for(int i=1;i<=s;++i){
		scanf("%d",&J[i]);
		for(int j=1;j<=J[i];++j)	scanf("%d%d",&x[i][j],&y[i][j]);
		scanf("%d",&P[i]);
	}
	cin>>b;
	for(int i=1;i<=b;++i)	scanf("%d%d%d",c+i,k+i,p+i),m[c[i]]=i;
	int f[10]={0};
	dfs(f,0);
	return cout<<ans,0;
}
2023/10/5 08:50
加载中...