把昨天没改完的码积木改完了,最终解法先发现一个性质是往上堆一个就算和下一个高度重叠也对下一个没有影响,所升序排完后设变量m(m初始等于a[1]),如果m比当前遍历到的a[i]大代表这个a[i]有重叠,更新答案,如果比a[i]小就让m=a[i]保持同频。
改完这题后又去改暑假的T3,就是一个n个元素为1~n且互不相同的双向队列但是可以从中间挑数放到队头队尾,最终让队列成为升序。赛时打了个90pts的暴力,大概思路是ans=n-最长上升序列长度(中间可以隔数字)直接n^2求长度,当然TLE。正解是开一个数组p表示下表为a[i]的数在队列中的位置,f[i]表示以数字i结尾的最长上升序列长度,初始值均为1,递推式是f[i]=f[i-1]+1,最后输出n-max(f[i])。