条件: 用严格单调的上升序列和下降序列来覆盖整个区间
目标:求能够覆盖整个区间的上升序列、下降序列加起来个数的最小值
我们这一题和拦截导弹 这一题有点像,但又不完全相同,多了一种单调升的决策
一般关于决策问题通常用dp或者dfs(暴搜)——都是以集合的形式记录最小值进行遍历
但是我们这一题的状态不好表示,所以直接用dfs
做法:在拦截导弹的贪心方向中加上另一个决策的贪心方法,在套一层暴搜
,贪心不懂的可以看这里拦截导弹
问题1:为什么bfs可以求最小值而不用它
因为bfs有以下缺点
1. 需要把所有路径都存下来(指数级),会爆栈
2. 不容易剪枝,不好进行优化
3. 代码复杂度高
问题2: 怎么用dfs求最小值
bfs第一次搜到的就是最小值,而dfs第一次搜到的不一定是最小值,所以要借助外部工具进行记录判断
方法1: 设置一个全局变量,不断更新来求最小值
方法2: 迭代加深
提醒: dfs需要恢复现场,所以记得先把初始值存下来,以备后面恢复现场
具体的代码和细节看下列代码的注释部分
代码1:用全局变量距离最小值+剪枝优化求最小值
设置最小值ans,最少的序列ans=最少的上升序列su+最少的下降序列sd
#include <iostream>
#include <algorithm>
using namespace std;
const int N=55;
int a[N];
int up[N],down[N];//up[]存储每段上升序列结尾数,down[]存储每段下降序列结尾数
int n;
int ans;//ans=su+sd,最少的序列=最少的上升序列+最少的下降序列
//参数1表示当前枚举到了第几个数,参数2表示当前上升子序列的个数,参数3表示当前下降子序列的个数
void dfs(int u,int su,int sd)
{
if(su+sd>=ans) return ;//因为上升和下降的加起来都>=ans,说明不能再变小
if(u==n)//否则su+sd<ans,此时如果u==n,说明找到了一个方案
{
ans=su+sd;
return ;
}
//case1:把当前数放到上升子序列中
int k=0;
//如果上升子序列的结尾>q[u],说明q[u]不能插入当前序列,k++遍历下一个序列
while(k<su && up[k]>=a[u]) k++;
int t=up[k];//因为dfs要恢复现场,所以用t存在初始值以备后面用
up[k]=a[u];
if(k<su) dfs(u+1,su,sd);//要判断有没有创建新的上升序列
else dfs(u+1,su+1,sd);
up[k]=t;
//case2:把当前数放在下降子序列中,与上面case1反着来就行
k=0;
while(k<sd&& down[k]<=a[u]) k++;
t=down[k];
down[k]=a[u];
if(k<sd) dfs(u+1,su,sd);
else dfs(u+1,su,sd+1);
down[k]=t;
}
int main()
{
while(cin>>n,n)
{
for(int i=0;i<n;i++)
cin>>a[i];
ans=n;//每次暴搜前赋值为n,因为最坏每个序列都是一个,所以ans=n
dfs(0,0,0);
cout<<ans<<endl;
}
return 0;
}
代码2:迭代加深
#include <bits/stdc++.h>
using namespace std;
const int N=55;
int up[N],down[N];
int n;
int a[N];
bool dfs(int depth,int u,int su,int sd)//depth表示所有序列数和的上限,u,su,sd和记录全局最小值的定义一样
{
if(su+sd>depth) return false;//如果层数用完了,说明没搜到最小值方案
if(u==n) return true;//如果层数还有,搜完了所有数,说明搜到了最小值方案
//枚举所有的选法
bool flag=false;//flag表示有没有把当前数a[u]归入当前某个子序列里
//枚举上升子序列
for(int i=1;i<=su;i++)
if(up[i]<a[u])//如果a[u]大于最小的结尾,说明可以放进去
{
int t=up[i];//记录初始值以便恢复现场
up[i]=a[u];
if(dfs(depth,u+1,su,sd)) return true;
up[i]=t;//恢复现场
flag=true;//说明放进去了
break;
}
if(!flag)//如果flag==false,说明没有放进去,需要开一个新组
{
up[su+1]=a[u];
if(dfs(depth,u+1,su+1,sd)) return true;
}
//枚举下降子序列,与上面反着来就行
flag=false;
for(int i=1;i<=sd;i++)
if(down[i]>a[u])//如果a[u]大于最小的结尾,说明可以放进去
{
int t=down[i];//记录初始值以便恢复现场
down[i]=a[u];
if(dfs(depth,u+1,su,sd)) return true;
down[i]=t;//恢复现场
flag=true;//说明放进去了
break;
}
if(!flag)//如果flag==false,说明没有放进去,需要开一个新组
{
down[sd+1]=a[u];
if(dfs(depth,u+1,su,sd+1)) return true;
}
return false;//所有选法都搜完了也没有解,返回false
}
int main()
{
while(cin>>n,n)
{
for(int i=0;i<n;i++)
cin>>a[i];
int depth=0;//迭代加深的层数
while(!dfs(depth,0,0,0)) depth++;//当前的层数下搜不到解,就下一层
cout<<depth<<endl;
}
return 0;
}