https://www.luogu.org/problem/show?pid=2258 做法：搜索+DP.. 复杂度O(2^n * n^3) 勉强能过..硬是给这题垃圾题调了几天.. [code lang="cpp"] #include<cstdio> #include<iostream> #include<cstring> #define MAXN 16 #define INF 1147483646 using namespace std; int g[MAXN][MAXN]; bool used[MAXN]; int nowr[MAXN]; int s[ […]

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

https://vijos.org/p/1369 求出现第K个数的（位置不变）LIS 思路： 把左边大于等于K的去掉，右边小于等于K的去掉 然后直接做LIS即可 注意n=300000，不能O(n^2)必须O(nlog n) [code lang="cpp"] #include<cstdio> #include<iostream> #define MAXN 333333 #define INF 2147483647 using namespace std; int dp[MAXN], a[MAXN], s[MAXN], g[MAXN]; int n, k, len = 2 […]

原题目：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) [code lang="cpp"] #include<cstdio> #include<iostr […]

【黑历史存档】内容已隐藏，仅限查看标题。

整场比赛我就不吐槽了..我就吐槽第二题.. MLGB O(4^n) n = 14, 3s能A??我服气..肯定是天河二号在从中作梗.. 这不就是给暴力的同志放水么.. 怪我不打暴力咯..... —————————————— 明天写题解,MLGB.

http://poj.org/problem?id=1088 https://vijos.org/p/1011 今天终于名正言顺地A掉了这一题，为什么说是名正言顺呢，因为之前做的我是半抄别人代码的，而现在我在没有任何提示（包括之前的记忆，已经忘掉了= =）的情况下半小时AC了这题..而且时间刚刚好是昨年..那时我用了三天，不多说，上代码:) 旧版: [code lang="cpp"] /*Source Code 2015-09-22 21:18:43 Problem: 1088 User: aclolicon Memory: 972K Time: 16MS Language: C++ Resu […]

地址：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(sum[s + i] - sum[s + i - k])} s是第一断点（断环的第一个，k为新增长度） 坑点就是j = 1的情况..也许是我的算法比较特殊需要特殊处理.. […]

背景 JerryZhou同学经常改编习题给自己做。 这天，他又改编了一题。。。。。 描述 设有N*N的方格图，我们将其中的某些方格填入正整数， 而其他的方格中放入0。 某人从图得左上角出发，可以向下走，也可以向右走，直到到达右下角。 在走过的路上，他取走了方格中的数。（取走后方格中数字变为0） 此人从左上角到右下角共走3次，试找出3条路径，使得取得的数总和最大。 格式 输入格式 第一行:N (4<=N<=20) 接下来一个N*N的矩阵，矩阵中每个元素不超过80，不小于0 输出格式 一行，表示最大的总和。 样例1 样例输入1 4 1 2 3 4 2 1 3 4 1 2 3 4 1 3 […]

活动视频