AcWing 187. 导弹防御系统
标签：col 序列 void include dfs pac amp std class
//dp+dfs+贪心
//记一个全局变量
#includeusing namespace std ;
const int N=55;
int n;
int ans;
int q[N];
int up[N],down[N];//表示上升子序列结尾和下降子序列结尾
void dfs(int u,int su,int sd)//u表示枚举到了第几个数字，su表示上升子序列个数，sd表示下降子序列个数
{
if(su+sd>=ans) return; //说明已经不可能再变小
if(u==n)//说明已经找到最后一个
{
ans=su+sd;
return ;
}
// 将当前数字放到上升子序列中
int k=0;
while(k=q[u]) k++;
int t=up[k];//备份，为了下面的深搜回溯恢复现场
up[k]=q[u];
if(k1,su,sd);
else dfs(u+1,su+1,sd);
up[k]=t;//恢复现场
//将当前数字放到下降子序列中
k=0;
while(k;
t=down[k];
down[k]=q[u];
if(k1,su,sd);
else dfs(u+1,su,sd+1);
down[k]=t;
}
int main() {
while(cin>>n,n) {
for(int i=0; i)
cin>>q[i];
ans=n;//先假设每个数字都是一个序列
dfs(0,0,0);
coutendl;
}
return 0;
}
AcWing 187. 导弹防御系统
标签：col 序列 void include dfs pac amp std class
原文地址：https://www.cnblogs.com/QingyuYYYYY/p/11961179.html
评论