2016-10-25
luoguP1541:NOIP2010提高组:乌龟棋

题目:https://www.luogu.org/problem/show?pid=1541 题意: 每个格子有一个值,可以有限定次数地走1,2,3,4步,求经过的格子的值总和 做法: 一开始想到的自然是n*k1*k2*k3*k4的DP,五维数组,内存可以滚动,但是时间复杂度... 后来发现其实可以直接忽略步数,直接开四维 dp[i][j][k][l]:分别用了几张卡片取得的值

阅读更多 →
代码
2016-10-21
NOIP2014普及 P2258:子矩阵

https://www.luogu.org/problem/show?pid=2258 做法:搜索+DP.. 复杂度O(2^n * n^3) 勉强能过..硬是给这题垃圾题调了几天..

阅读更多 →
未分类
2016-10-12
[SCOI2005]P2327:扫雷

https://www.luogu.org/problem/show?pid=2327 做法: dp.dp[i][j]表示到第i位的附近三格,有几种形状为j的可能 “形状为j”是什么意思呢,注意到如果附近三格有无雷用0,1表示的话,其实就组成了二进制数字,把他们转化为十进制即为j 那么j最大是7 转移的话直接根据上一次结果和当前数字判断即可,我用了滚动数组 O(n)  

阅读更多 →
代码
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-10-02
L站复活+搬家

在Bytecat和本人的努力下,L站搬了家,又复活啦... www.lililili.net 预祝DDos本站的人早日爆炸

阅读更多 →
消息
没有更多文章了...