2019年1月21日训练日记

今天看的题不多,也都没能做出来。。。

其中有一个问题是这样的:2080 最长上升子序列:
一个数列的最长上升子列,是指其所有递增的子列中最长的一个子列
给定一个长度为 n 的数列 an,求这个数列的最长上升子列的长度
例如对数列 1 7 2 8 3 4,这个数列的最长递增子数列是 1 2 3 4,长度为 4;次长的长度为 3, 包括 1 7 8、1 2 3 等。

对于解这道题时,一开始的思路就出现了错误。。。
定义了两个循环,如果后面的数出现比前面大的,就累加计数,与此同时,计数过程甚至也出了一些问题,例如以上数列1 7 2 8 3 4,累加时初值应为1,因为序列比较后需要加前面的一个值,因此应从一开始计数而并非零,但是出现的问题是每次进行循环时如果出现第二个数,第三个数都比第一个数大,第三个数又比第二个数小时,会出现计数错误,又试着多加几次循环但是仍然解决不了这个问题,写到这里突然想到是否可以在数组中附加条件使得前一项必须小于后一项时再进行累加,一会去试试。。。
其实上面这个问题其他人选择的做法都是使用了数位dp;对于这个问题也恐怕要先学习一下才更能方便做。

还有一个题是这样的:
2103 四舍六入五留双 :
输入一个实数f,和一个位数d
输出实数f,在保留d位小数下的结果,采用四舍六入五留双的近似。
f至多有30位小数。
0 <= f <= 1
1 <= d <= 8
所谓四舍六入五留双,是指如果恰好是0.5的情况,会把他近似到使得前一位是偶数。
比如近似到整数,0.4为0,0.5为0,0.50001为1,0.6为1,1.5为2,2.5为2。

好像挺经典的一个经济类运算问题,很多取余的方式好像就用的这种。
如果能有像%那样的能对实型取余的符号这个题就会变得简单,我觉得这个题难就难在对小数位的取余问题,如何将小数放大到整数,再去判定后面的小数部分与0.5的大小关系,这个好像是算法问题,或许是我天生愚钝,想了很久就是去不掉。或许我想的太复杂了,我想的f并没有局限性,不只是在0~1,我直接想在实型范围内怎么去简化,怎么去取余。。。

对于做不出的题也很失望。。。
或许是有的知识点还没有学到,也或许是该看看书了。。。
明天去看看字符串,数位,简单算法题的知识点,能看多少看多少。。。

原文地址:https://www.cnblogs.com/study-hard-forever/p/12130081.html