这题用排列树能做吗,能的话怎么剪枝啊,全是TLE
查看原帖
这题用排列树能做吗,能的话怎么剪枝啊,全是TLE
569087
passing_dragon楼主2021/11/11 19:09
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;//排列树,排列后的模拟
int s1 = 0,s2 = 0,s3 = 0,s4 = 0;
int A[65],B[65],C[65],D[65];
int ans[5];
int Calculate(int,int*);
void SeekAns(int t,int s,int *x,int num)//t present num   num 枚举到的题库 
{
	if(t >= s)
	{
		int temp = Calculate(s,x);
		ans[num] = ans[num]<temp?ans[num]:temp;
	}
	for(int i = t; i < s; i++)
	{
		swap(x[i],x[t]); 
		SeekAns(t + 1,s,x,num);//超时后在想剪枝 
		swap(x[i],x[t]);
	}
}
int Calculate(int s,int* x)//模拟计算所需时间 
{
	 int stack[3];
	 int top = 0;
	 stack[0] = x[0];
	 top++;
	 int sum = 0;
	 for(int i = 1; i < s; i++)
	 {
	 	int temp = stack[--top];
	 	sum += min(temp,x[i]);
	 	temp = abs(temp - x[i]);
	 	stack[top++] = temp;
	 }
	 sum += stack[0];
	 return sum;
} 
void Put(int n, int *Time)
{
	for(int i = 0; i < n; i++)
	cin>>Time[i];
}
int main()
{
	cin>>s1>>s2>>s3>>s4;
	Put(s1,A);
	Put(s2,B);
	Put(s3,C);
	Put(s4,D);
	memset(ans,0x3f3f3f,sizeof(ans));
	SeekAns(0,s1,A,0);
	SeekAns(0,s2,B,1);
	SeekAns(0,s3,C,2);
	SeekAns(0,s4,D,3);
	int Ans = 0;
	for(int i = 0; i < 4; i++)
	Ans += ans[i];
	cout<<Ans<<endl;
} 
2021/11/11 19:09
加载中...