求助爆搜TLE
查看原帖
求助爆搜TLE
285617
黑影洞人楼主2022/8/5 16:57
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#define N 25
using namespace std;
int n,a,b,ans=155,li[N],lis[N],res[N],arr[N];
bool die[N];
bool check(){
	for(int i=1;i<=n;i++)if(!die[i])return 0;
	return 1;
}
inline void dfs(int x,int dep){
	//printf("%d %d %d\n",x,dep,ans);
	if(x==0)return;
	if(dep>=ans)return;
	li[x]-=a;li[x-1]-=b,li[x+1]-=b;
	lis[dep]=x;
	for(int i=1;i<=n;i++){die[i]=0;if(li[i]<0)die[i]=1;}
	if(check()){
		if(dep<ans){
			for(int i=1;i<=dep;i++)res[i]=lis[i];
			ans=dep;
		}
		li[x]+=a;li[x-1]+=b,li[x+1]+=b;
		for(int i=1;i<=n;i++){die[i]=0;if(li[i]<0)die[i]=1;}
		return;
	}
	random_shuffle(arr+2,arr+n);
	for(int i=2;i<n;i++){
		int y=i;
		if(die[i]==1&&die[i-1]==1&&die[i+1]==1)continue;
		dfs(arr[i],dep+1);
	}
	li[x]+=a;li[x-1]+=b,li[x+1]+=b;
	for(int i=1;i<=n;i++){die[i]=0;if(li[i]<0)die[i]=1;}
}
signed main(){
	srand(time(0));
	scanf("%d%d%d",&n,&a,&b);
	for(int i=1;i<=n;i++)arr[i]=i,scanf("%d",&li[i]);
	for(int i=2;i<n;i++){
		for(int i=1;i<=n;i++)die[i]=0;
		dfs(i,1);
	}
	int ress=0;
	for(int i=1;i<=ans;i++)ress+=(res[i]>1&&res[i]<n);
	printf("%d\n",ress);
	for(int i=1;i<=ans;i++)if(res[i]>1&&res[i]<n)printf("%d ",res[i]);
	return 0;
}



2022/8/5 16:57
加载中...