欢迎大家访问我的老师的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>h呢?
其实这句话本意是为了找到非递减序列中,最后一个数最接近a[idx]的序列,将数安排进这个队列里。
也可以利用贪心的思想来证明:
设现有两个数x1,x2,x2后于x1插入队列,现有两个非递减队列最后末尾数s1,s2,且s1<x2<s2<x1,此时最优解就是2.
但如果将x1插入s1所在队列中,则会导致此时解为3.
所以我们可以得出一个结论:
对于较大的数要进入非递减序列中,我们要将它放在众多序列中末尾数最大的序列上。
因为这样可以使未来较小的数,有更多的机会进到队列中去,而不是选择去新开队列。
同样,对于非递减队列也是如此。
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;
}