Python
Java
PHP
IOS
Android
Nodejs
JavaScript
Html5
Windows
Ubuntu
Linux
Thief in a Shop 【CodeForces - 632E】【背包】
题目链接 给了N个物品 每个物品无限个 我们要的是求刚好我们拿了K个物品的时候 能组成哪几种数 我们可以想个办法去填充 那么就需要有一个所谓的0状态 然后假如不足K个的时候 就可以拿这个所谓的0状态来填充了 所以 我们把所有的数排序 然后都
DP动态规划
背包
动态规划
DP
Puzzles【Codeforces 697 D】【树形DP + 期望DP】
Codeforces Round 362 Div 2 D 我们从1号结点开始 给每个结点标序 问的是每个结点的序号的期望是多少 输出这N个结点的期望 那么1号点的期望一定就是1了 对于其他的点呢 可以举例这样的一幅图 首先我们可以确定1 因
DP动态规划
Codeforces
期望DP
Palindrome subsequence【区间DP+冗斥】
题目链接HDU 4632 题目让我们求给定的一段字符串上回文串的长度 一个数也算是回文串 于是我就想怎样去找其中的规律 我举了些例子 先是从相同的字符串开始举例 aaa 对于aaa dp 1 1 1 dp 2 2 1 dp 1 2 dp 1
DP动态规划
冗斥
DP
区间dp
Crazy Thairs【树状数组+高精度+DP思想】
题目链接 POJ 3378 题意 有N个点 问的是要求组成一个长度为5的上升子序列的组成有多少种 最搞事情的是这道题不用取模 所以 是一定会爆long long的 首先 很容易想到一点就是我们可以开一个dp maxN 5 表示的是 dp i
数据结构
DP动态规划
树状数组
离散化
高精度
Rabbit的工作(2)【牛客练习赛36_C + dp背包】
题目链接 那么的巧合 竟是这题的原题 就是 我们既然一定要选取K个任务 就先去取K个任务 然后逐一加上需要的额外天数即可 include
DP动态规划
背包
骰子【概率dp】
题目链接 P1409 骰子 因为会有人被弹出队列 所以我设置的期望dp为 表示当现在队列中有i个人的时候 第j个人获胜的概率 于是有当只剩一个人的时候 那个人必胜 再往下 先看它在队首的情况 也就是直接获胜的概率加上它被弹到队尾时候的概率
DP动态规划
概率
DP
Nikitosh and xor【字典树+dp】
题目链接 比较明显的 正向一个推过去的字典树 再反向退回来的一个字典树 然后异或和用差分的方式解决 字典树一定是要从第29位开始往下的 千万别从第0位往上 include
DP动态规划
数据结构
字典树
DP
Economic Difficulties【DP】【Codeforces 1263 F】
Codeforces Round 603 Div 2 F 题意 给你两棵树 结点分别是1 A与1 B 然后给了N台设备 并且A树和B树的叶子结点都是链接设备的 问的是 我们最多可以割几条边使得每个设备都能链接A树或者B树上任意的一个 1 号
DP动态规划
DP
The Lost House【树形DP+期望+构造路径】
题目链接 POJ 2057 题意 有一棵N的点的树 开始的时候蜗牛在1号结点 它不知道它的家在哪个叶子结点 树上的有些结点有虫虫 虫虫会告诉你 你的家是否在以它所在结点为根的子树上 现在需要你规划走的方案 使得找到哪个叶子结点才是家的所走路
DP动态规划
树形DP
期望
构造
过河 【状态压缩DP】+【完整的数论推导过程】
题目链接 题意 很多人以为青蛙是要跳到石头上 一个个往后跳 问最少需要的石头数量 其实不然 题目给的样例的确也是有些坑了 青蛙每次都有跳的距离范围 题目求的是最少会跳到的石头 青蛙可以在水中起跳 它要尽可能的避开石头 也就是问抵达终点时最少
DP动态规划
拓展欧几里得算法
数论
状态压缩
DP
石子合并(区间DP问题)
题目描述 设有 N 堆石子排成一排 其编号为 1 2 3 N 每堆石子有一定的质量 可以用一个整数来描述 现在要将这 N 堆石子合并成为一堆 每次只能合并相邻的两堆 合并的代价为这两堆石子的质量之和 合并后与这两堆石子相邻的石子将和新堆相邻
DP动态规划
Daniel and Spring Cleaning【数位DP】【Codeforces 1245 F】
Codeforces Round 597 Div 2 F 这道题化简一下就是让我们求有上下限的2进制数中有几对满足每一位的相 值不为1的对数 那么 首先看到这个1e9就会让人想到数位DP 然后接着就是如何去求的这样一个问题 我们不如将上下限
DP动态规划
Codeforces
数位dp
[NOI Online #3 入门组 T3]买表【二进制优化dp背包】
题目链接 很可惜的一点就是 我正赛的时候好像把a和k看反了 于是一直想不到如何做 打了个暴力分 现在想想 暴力分也错了 因为a和k真的很关键 使得最后300变成200分 人生第一场OI就这样草草结束 或许这就是OI选手的刺激所在吧 得亏我不
DP动态规划
背包
二进制优化
DP
Wireless Password 【HDU - 2825】【AC自动机+状压DP】
题目链接 好题一道 推了一会 然后计算了一下时间复杂度 差不多最坏情况是25 100 1024 26 66560000然后看了下 嗯 能搞 有搞头哈哈哈 然后写了一下 首先 WA了 发现竟然是最大极限哪儿写错了 我的个天呐 A 我们看到最多
DP动态规划
数据结构
AC自动机
DP
免费馅饼【暑期集训I题】【经典DP】
这不是一道很废脑汁的题目 可以说和前面的数塔相同 只是题目讲的长了些而已 都说天上不会掉馅饼 但有一天gameboy正走在回家的小径上 忽然天上掉下大把大把的馅饼 说来gameboy的人品实在是太好了 这馅饼别处都不掉 就掉落在他身旁的10
DP动态规划
记忆化搜索
DP
Clannad【2018四川省赛】【AC自动机 + DP】
题目链接 第十届四川省赛C题 挺好的一道题 就是要做一个last优化 每次的last要返回到之前的有值节点 也就是单词的尾的对应节点 然后就不会超时了 呜呜呜 之前一直超时 以为是初始化的memset 问题 以前被卡过memset 然后发现
数据结构
AC自动机
DP动态规划
Beautiful Mirrors【Codeforces 1265 E】【期望DP】
Codeforces Round 604 Div 2 E 题记 不是杭电今年份的原题嘛 为什么比赛的时候没想到这个方面呢 当然题也读错了 尬 杭电多校原题 然后再继续说一下这道题的特殊之处吧 随便说说 典型问题 没有特殊之处 大概画了个图
DP动态规划
期望DP
DNA repair 【HDU - 2457】【AC自动机+DP思路】
题目链接 开始肝这道题的时候也是冒了十足的勇气 呜呜呜 当时一直没发现 我有个地方写成了 s i A 怎么能这样用啊 毕竟只有A C G T的说 呜呜呜 QAQ 然后讲一下 这道题的AC自动机的想法 还有DP的思路 我DP超菜 能过也是超神
DP动态规划
数据结构
AC自动机