Missile Defence System[POJ3700]

欢迎大家访问我的老师的OJ———caioj.cn

题面描述

传送门

思路

首先我们要限制搜索深度。
由题意可知,我们需要多个非递增或非递减的序列来覆盖所有导弹(有时间顺序)
对于我们当前状态,我们选择先找到一个非递增或非递减的序列将它填进去。
或者后新建一个非递增或非递减的序列将它填进去。
利用贪心的思想可以很容易证明上面结论。
为了方便,我们同一定义先进行非递减序列插入操作。

int h=0,choice=0;//up
bool v_up=false;
for(int i=1;i<=m;i++)
{
	int tail=f[i][0];
	int state=f[i][1];
	if(tail<=a[idx]&&tail>h&&state==0)
	{			
		h=tail;choice=i;
	}
}

这里为什么要tail&gt;h\operatorname{tail&gt;h}tail>h呢?
其实这句话本意是为了找到非递减序列中,最后一个数最接近a[idx]a[idx]a[idx]的序列,将数安排进这个队列里。
也可以利用贪心的思想来证明:
设现有两个数x1,x2x_1,x_2x1​,x2​,x2x_2x2​后于x1x_1x1​插入队列,现有两个非递减队列最后末尾数s1,s2s_1,s_2s1​,s2​,且s1&lt;x2&lt;s2&lt;x1s_1&lt;x_2&lt;s_2&lt;x_1s1​<x2​<s2​<x1​,此时最优解就是222.
但如果将x1x_1x1​插入s1s_1s1​所在队列中,则会导致此时解为333.
所以我们可以得出一个结论:
对于较大的数要进入非递减序列中,我们要将它放在众多序列中末尾数最大的序列上。
因为这样可以使未来较小的数,有更多的机会进到队列中去,而不是选择去新开队列。

同样,对于非递减队列也是如此。

for(int i=1;i<=m;i++)\\down
	{
		int tail=f[i][0];
		int state=f[i][1];
		if(tail>=a[idx]&&tail<h&&state==1)
		{
			h=tail;choice=i;
		}
	}

若两种方案都不行
则新开队列。

if(!v_up)
	{
		f[++m][0]=a[idx];
		f[m][1]=0;
		if(dfs(idx+1))return true;
		--m;
	}
	if(!v_down)
	{
		f[++m][0]=a[idx];
		f[m][1]=1;
		if(dfs(idx+1))return true;
		--m;
	}

完整代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
using namespace std;
const int N=110;
int f[N][2],a[N];
int n,m,ans;
bool dfs(int idx)
{
	if(m>ans)return false;
	if(idx==n+1)return true;
	int h=0,choice=0;//up
	bool v_up=false,v_down=false;
	for(int i=1;i<=m;i++)
	{
		int tail=f[i][0];
		int state=f[i][1];
		if(tail<=a[idx]&&tail>h&&state==0)
		{
			h=tail;choice=i;
		}
	}
	if(choice)
	{
		f[choice][0]=a[idx];
		if(dfs(idx+1))return true;
		f[choice][0]=h;
		v_up=true;
	}
	h=1e9;choice=0;
	for(int i=1;i<=m;i++)
	{
		int tail=f[i][0];
		int state=f[i][1];
		if(tail>=a[idx]&&tail<h&&state==1)
		{
			h=tail;choice=i;
		}
	}
	if(choice)
	{
		f[choice][0]=a[idx];
		if(dfs(idx+1))return true;
		f[choice][0]=h;
		v_down=true;
	}
	if(!v_up)
	{
		f[++m][0]=a[idx];
		f[m][1]=0;
		if(dfs(idx+1))return true;
		--m;
	}
	if(!v_down)
	{
		f[++m][0]=a[idx];
		f[m][1]=1;
		if(dfs(idx+1))return true;
		--m;
	}
	return false;
}
int main()
{
	while(scanf("%d",&n)&&n)
	{
		ans=1;
		for(int i=1;i<=n;i++)scanf("%d",&a[i]);
		while(1)
		{
			m=0;
			if(dfs(1))break;
			ans++;
		}
		printf("%d\n",ans);
	}
	return 0;
}
上一篇:找到链表的倒数第n个结点


下一篇:poj1015 Jury Compromise