导弹防御系统
为了对抗附近恶意国家的威胁，R国更新了他们的导弹防御系统。
一套防御系统的导弹拦截高度要么一直 严格单调 上升要么一直 严格单调 下降。
数据范围
1≤n≤50
输入样例：
5 3 5 2 4 1 0输出样例：
2样例解释
对于给出样例，最少需要两套防御系统。
一套击落高度为3,4的导弹，另一套击落高度为5,2,1的导弹。
#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N=55; int h[N],up[N],down[N],ans,n;//up[i]存的是第k套拦截系统拦截的最后一发导弹 void dfs(int u,int d,int t)//这题最妙的地方在于第一个找到的就是最合适的 //加入一个数要加入到上升序列中， //则一定要选择最后一发导弹值最大的那个序列加进去， //因为你最大的都能加进去，小的一定也能进去，给其他的腾出点空间 //神奇的是，你在1~u中的up序列中找到的第一个就是高度最高的导弹， //因为如果高度不够就会另开一个数组，再开的数组高度一定不如前面， //因为就是因为高度不够才重开的 //后面就是经典的选择+回溯了 { if(u+d>=ans)return; if(t==n) { if(u+d<ans)ans=u+d; } int i; for(i=1;i<=u;i++) { if(h[t]>up[i])break; } int temp=up[i]; up[i]=h[t]; dfs(max(u,i),d,t+1); up[i]=temp; for(i=1;i<=d;i++) { if(h[t]<down[i])break; } temp=down[i]; down[i]=h[t]; dfs(u,max(d,i),t+1); down[i]=temp; } int main() { while(cin>>n,n) { ans=0x3f3f3f3f; for(int i=0;i<n;i++) cin>>h[i]; dfs(0,0,0); cout<<ans<<endl; } }
