1010. 拦截导弹（dp模版二 最长上升子序列

题源求导弹的可拦截个数是最长下降子序列求导弹的发射个数是最长上升子序列证明是一个定理#includebits/stdc.husingnamespacestd;constintN1009;intarr[N],dpDe[N],dpIn[N],tot0;intansDe0,ansIn0;intmain(){intansDe0,ansIn0;while(cinarr[tot]){}//couttotendl;for(inti1;itot;i){dpDe[i]1;dpIn[i]1;for(intj1;ji;j){if(arr[j]arr[i]){dpIn[i]max(dpIn[j]1,dpIn[i]);// coutarr[j] arr[i] dpIn[j] dpIn[i]endl;}if(arr[j]arr[i]){dpDe[i]max(dpDe[j]1,dpDe[i]);}}ansDemax(dpDe[i],ansDe);ansInmax(dpIn[i],ansIn);}coutansDe\nansIn;return0;}