网页制作与网站建设设计价格,国土资源部门网站建设制度,找别人做网站要注意什么软件,十堰市茅箭区建设局网站导弹防御系统
题意#xff1a;
最少可以找到一直 严格单调 上升或者一直 严格单调 下降
题解#xff1a;
第一反应是LIS#xff0c;但是本题要求找一直上升或者一直下降的#xff0c;LIS不能实现 但是我们还是从LIS下手#xff0c;LIS中最核心的思想是能否将一个元素加…导弹防御系统
题意
最少可以找到一直 严格单调 上升或者一直 严格单调 下降
题解
第一反应是LIS但是本题要求找一直上升或者一直下降的LIS不能实现 但是我们还是从LIS下手LIS中最核心的思想是能否将一个元素加入到序列中只与这个序列目前的最后一个元素有关 我们用up[k]和down[k]记录第k套上升下降系统目前所拦截的最后一个导弹 dfs(u,v,t)表示已有u个上升v个下降正在处理第t个数 现在我们要将一个数放入上升序列中那么一定是所有能放入的上升序列中最后一个元素最大的那一个这样求答案节省时间 因为放在最大的里面就不会浪费小的就把小的让给更需要的数就是每个数都往“条件最差”的情况里放 up[i]按照这样的策略顺序自然就是排好的所以只能找最先碰到的一个选择
代码
#includebits/stdc.h
typedef long long ll;
using namespace std;
inline int read(){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9) ss*10ch-0,chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
const int maxn60;
int a[maxn],up[maxn],down[maxn],n;
int ans;
void dfs(int u,int d,int t)
{if(udans)return ;if(tn){if(udans)ansud;return ;}int i;for(i1;iu;i)//找到第一个末尾数小于a[t]的导弹系统if(up[i]a[t])break;int tempup[i];up[i]a[t];//添加到该导弹系统中i有可能是之前已有的也可能是新的导弹系统 dfs(max(u,i),d,t1);//有可能第t个数在某个序列后面也有可能自己成一个序列up[i]temp;//恢复原状 for(i1;id;i)if(down[i]a[t])break;tempdown[i];down[i]a[t];dfs(u,max(d,i),t1);down[i]temp;//恢复原状
}
int main()
{while(cinnn!0){ans200;for(int i0;in;i)cina[i];dfs(0,0,0);coutansendl;}return 0;
}
