2016-10-10
vijos1369:nlogn的LIS

https://vijos.org/p/1369 求出现第K个数的(位置不变)LIS 思路: 把左边大于等于K的去掉,右边小于等于K的去掉 然后直接做LIS即可 注意n=300000,不能O(n^2)必须O(nlog n)

阅读更多 →
代码
2016-10-09
Vijos1264:神秘的咒语(LIS+LCS)

原题目:https://vijos.org/p/1264 题意:求两组数的最长上升公共子序列。 我的做法: 脑残级DP: dp(i, j) = max{dp(i - 1, k)} , a[i] == b[j] & b[j] < b[k] = dp[i - 1][j], a[i] != b[j] 然后开三层循环..O(m^3) 然后0.5s过了.. 然后发现网上大神有O(m^2)做法.. Orz..这么简单的优化我也想不到.. 我已经是条咸鱼了.. 我的O(m^3) 优化后的O(m^2) 不过算是 …

阅读更多 →
代码
2016-09-20
vijos1011&poj1088:记忆化搜索+DP【名正言顺的AC】

http://poj.org/problem?id=1088 https://vijos.org/p/1011 今天终于名正言顺地A掉了这一题,为什么说是名正言顺呢,因为之前做的我是半抄别人代码的,而现在我在没有任何提示(包括之前的记忆,已经忘掉了= =)的情况下半小时AC了这题..而且时间刚刚好是昨年..那时我用了三天,不多说,上代码:) 旧版: 今晚的: 虽然用时稍长,但是今晚值得庆祝..

阅读更多 →
代码
2016-09-18
vijos1218:环形DP

地址:https://vijos.org/p/1218 题意:在你面前有一圈整数(一共n个),你要按顺序将其分为m个部分,各部分内的数字相加,相加所得的m个结果对10取模后再相乘,最终得到一个数k。游戏的要求是使你所得的k最大或者最小。 我的做法: 环形DP。先割环为链,枚举断点。 dp[i][j]:取长度为i割为j段能获得的最小(最大)值。 那么dp[i][j] = max{dp[i - k][j - 1] * chuli(su …

阅读更多 →
代码
2016-09-11
[vijos]P1143:三取方格数(多进程DP)

背景 JerryZhou同学经常改编习题给自己做。 这天,他又改编了一题。。。。。 描述 设有N*N的方格图,我们将其中的某些方格填入正整数, 而其他的方格中放入0。 某人从图得左上角出发,可以向下走,也可以向右走,直到到达右下角。 在走过的路上,他取走了方格中的数。(取走后方格中数字变为0) 此人从左上角到右下角共走3次,试找出3条路径,使得取得的数总 …

阅读更多 →
代码
没有更多文章了...