【题解】abc216

C考虑从后往前推,即若此数为14,发现能被而除尽,则/2。7不能除尽,则-1。同时将这些步骤存在stack中,输出即可。#include<bits/...     阅读全文
nodeee 8月30日
0 评论

【题解】自然数拆分

题目链接解题思路本题dpi表示的是有i个数字和为j,由于每个i都是不断更新的,不会访问之前的i,所以可以直接滚动数组:dp[j]代表当前数字和为j。代码#...     阅读全文
nodeee 2020年11月19日
0 评论

【题解】跳房子

题目链接解题思路这题挺有意思的,看一看是可以在20分钟内想到解法,但是在实现的过程中会遇到很多阻碍。乍一看题面,问的是“至少”,那可以判断出这题大概率是道...     阅读全文
nodeee 2020年11月01日
0 评论

【题解】摆渡车

题目链接解题思路正解是斜率优化,但是我不会很容易想到是以时间作为下标dp的。但是由于时间复杂度会超,我们发现有用时间只有nm。所以对于其他的t-nm的时间...     阅读全文
nodeee 2020年09月23日
0 评论

【题解】分级

题目链接解题思路本题有一个引理:在满足S最小化的前提下,一定存在一种构造序列B的方案,使得B中的数值都在A中出现过。若想证明,请看《算法竞赛进阶指南》26...     阅读全文
nodeee 2020年09月13日
0 评论

【dp】乌龟棋

乌龟棋解题思路大佬们可能会疑惑为什么我放一道这么简单的dp在这里。首先是因为我dp特别弱,普及dp都做不出。。。第二是因为这道题有一个特点:数据范围很小。...     阅读全文
nodeee 2019年10月24日
0 评论

最短Hamilton路径

题面描述给定一张 $n$ 个点的带权无向图,点从 $0$ 到 $n-1$ 标号,求起点 $0$ 到终点 $n-1$ 的最短Hamilton路径。Hamil...     阅读全文
nodeee 2019年07月23日
0 评论

数的划分

数的划分解题思路这道题可以用dp也可以用dfs做,因为这道题目的数据范围很小。我们用$ dp[i][j] $表示将i划分成j份的可能数我们将状态转移方程列...     阅读全文
nodeee 2019年05月31日
0 评论

最长公共上升子序列的DP解法及其优化

定义状态Fi表示以a串的前i个整数与b串的前j个整数且以b[j]为结尾构成的LCIS的长度。状态转移方程:①Fi = Fi-1 (a[i] != b[j]...     阅读全文
nodeee 2019年04月25日
0 评论

AtCoder Tenka1 Task D: Three Colors

英文题面Problem StatementYou are given N integers. The i-th integer is ai. Find t...     阅读全文
nodeee 2019年04月21日
1 评论

混合背包

传送门题面描述【问题描述】一个旅行者有一个最多能用V公斤的背包,现在有n件物品,它们的重量分别是$ W_1,W_2,...,W_n $,它们的价值分别为$...     阅读全文
nodeee 2019年04月11日
0 评论

状态压缩

如果有一个状态,是由很多(<20)个状态组合起来的,就可以用状态压缩减少空间复杂度。我们把每一个子状态作为二进制的一位,可以表示其是和否。例题传送门...     阅读全文
nodeee 2019年04月08日
0 评论