加成序列

思路

可以暴搜.每一次选一个数,如果它可以由前面的两个数组成，就继续向下搜，直到末尾为n.

但可能状态层数很小,却比较靠后.这样会浪费大量时间.所以我们可以使用迭代加深,每次限制层数.虽然也搜到了许多无用状态,但和下一层相比就很小了

代码

#include<bits/stdc++.h>
using namespace std;
int n,len,f[100];
bool pd(int u)
{
	for(int i=1;i<u;i++)
	{
		for(int j=1;j<u;j++)
		{
			if(f[i]+f[j]==f[u]) return true;
		}
	}
	return false;
}
bool dfs(int u)
{
	if(u==len+1) return true; 
	if(u==1)
	{
		f[u]=1;
		if(dfs(u+1))return true;
	}
	if(u==len)
	{
		f[u]=n;
		if(!pd(u)) return false;
		if(dfs(u+1))return true;
	}
	for(int i=f[u-1]+1;i<n;i++)
	{
		f[u]=i;
		if(!pd(u)) continue;
		if(dfs(u+1))return true;
	}
	return false;
}
int main()
{
	while(cin>>n&&n)
	{
		memset(f,0,sizeof f);
		if(n==1) 
		{
			cout<<1<<endl;
			continue;
		}
		for(len=2;len<=n;len++) 
		{
			if(dfs(1)) break;
		}
		for(int i=1;i<=len;i++) cout<<f[i]<<" ";
		cout<<endl; 
	}
}

送礼物

思路 这是一道背包题.但体积太大,所以只能暴搜.可$2^{45}$也会超时，怎么办呢？可以双向搜索，先搜索一半,再搜索一半,最后二分，时间复杂度$T(2^x(n-x)+2^{n-x}*(n-x))$

$2^{22}*23+2^{23}*23=2^{26}+2^{27}$ $2^{23}*22+2^{22}*22=2^{27}+2^{26}$ $2^{24}*21+2^{21}*21=2^{28}+2^{25}$ 代码

#include<bits/stdc++.h>
using namespace std;
int n,w,a[50],k,lw[(1<<25)+10],cnt,ans;
void dfs1(int u,int sum)
{
	if(u==k+1)
	{
		lw[++cnt]=sum;
		return;
	}
	dfs1(u+1,sum);
	if((long long)sum+(long long)a[u]<=w) dfs1(u+1,sum+a[u]);
}
void dfs2(int u,int sum)
{
	if(u==n+1)
	{
		int l=1,r=cnt;
		while(l<r)
		{
			int mid=(l+r+1)/2;
			if(lw[mid]<=w-sum) l=mid;
			else r=mid-1;
		}
		ans=max(ans,lw[l]+sum);
		return;
	}
	dfs2(u+1,sum);
	if((long long)sum+(long long)a[u]<=w) dfs2(u+1,sum+a[u]);
}
int main()
{
	cin>>w>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	k=n/2+2;
	dfs1(1,0);
	sort(lw+1,lw+1+cnt);
	cnt=unique(lw+1,lw+1+cnt)-lw-1;
	dfs2(k+1,0);
	cout<<ans;
}

巴士

思路

代码

#include<bits/stdc++.h>
using namespace std;
int n,a[310],idx,flag[65],len=1;
struct bus
{
	int ft;
	int d;
	int cs;
};
bus buses[3700];
bool cmp(bus a,bus b)
{
	return a.cs>b.cs;
}
bool check(int i,int j)
{
	int idx2=0;
	while(i+idx2*j<60) 
	{
		if(!flag[i+idx2*j]) return false;
		idx2++;
	}
	if(idx2==1) return false;
	return true;	
}  
bool dfs(int u,int num,int sum)
{
	if(sum==n) return true;	
	
	if(u>len) return false;
	if(sum+(len-u+1)*buses[num].cs<n) return false; 
	for(int i=num;i<=idx;i++)
	{
		if(check(buses[i].ft,buses[i].d))
		{
			int idx2=0;
			while(buses[i].ft+idx2*buses[i].d<60) 
			{
				
				flag[buses[i].ft+idx2*buses[i].d]--;
				idx2++;
			}
			if(dfs(u+1,i,sum+buses[i].cs)) return true;
			idx2=0;
			while(buses[i].ft+idx2*buses[i].d<60) 
			{
			
				flag[buses[i].ft+idx2*buses[i].d]++;
					idx2++;
			}
		}
	}
	return false;
}

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) 
	{
		cin>>a[i];
		flag[a[i]]++;
	}
	for(int i=0;i<60;i++)
	{
		for(int j=i+1;j<=60;j++)
		{
			if(!check(i,j)) continue;
			buses[++idx].ft=i;
			buses[idx].d=j;
			buses[idx].cs=(59-i)/j+1;
		}
	}
	sort(buses+1,buses+1+idx,cmp);
	while(1)
	{
		if(dfs(1,1,0))  break;
		len++;
	}
	cout<<len;
}

导弹防御系统

思路

代码

#include<bits/stdc++.h>
using namespace std;
int n,a[60],u[60],d[60],ans;
void dfs(int t,int up,int down)
{
	if(up+down>=ans) return;
	if(t==n+1)
	{
		ans=min(ans,up+down);
		return;
	}
	int idx=1;
	while(idx<=up&&a[t]<=u[idx]) idx++;
	int u2=u[idx];
	u[idx]=a[t];
	if(idx>up) dfs(t+1,up+1,down);
	else dfs(t+1,up,down);
	u[idx]=u2;
	
    idx=1;
	while(idx<=down&&a[t]>=d[idx]) idx++;
	int d2=d[idx];
	d[idx]=a[t];
	if(idx>down) dfs(t+1,up,down+1);
	else dfs(t+1,up,down);
	d[idx]=d2;
	return;
} 
int main()
{
	while(cin>>n&&n)
	{
		ans=1000000;
		for(int i=1;i<=n;i++) cin>>a[i];
		dfs(1,0,0);
		cout<<ans<<endl;
	}
}