关于
联系
本站已运行
载入天数...载入时分秒...
本站 CDN 服务由 提供
Woshiluo's Notebook
Codeforces Round #538 (Div. 2) 解题报告
2019年2月13日 / 周三 / 0 条评论

A Got Any Grapes? 顺序判断即 比赛的时候忘记写 else 既然 PP 了,然后就 FST #include <cstdio> int an,dm,mi; int gr,pu,bl; int main(){ scanf("%d%d%d", &an, &dm, &mi); scanf("%d%d%d", &gr, &pu, &bl); if(an > gr) { printf("NO\n"); r ...
 


树形背包 — Luogu P1273 有线电视网
2018年10月09日 / 周二 / 0 条评论

0x01 写在开头 题目链接:[https://www.luogu.org/problemnew/show/P1273] 前置技能 : 树形DP 如果做过选课的话,想必各位一看到就知道这是一道树形DP的题目 0x02 题目 题目中要求我们在以收入$\geq 0$的前提下,支持尽可能多的叶子节点 因此我们可以这么定义一个类似背包状态转移方程 $$ f(now,i+j)=m ...
 


图论天坑 题目 题目链接: [https://www.luogu.org/problemnew/show/P2272] 题目索然看起来好像很清楚的样子,然而没人我知道中间的问号有什么用,直到我去网上查了一回 对于一张图G,它中间任意取上两个点u,v其中有一条u到 v 或者 v 到 u 的边,我们就称这张图为半连通图 如果从一张图G选出任意几个点与这几个点有关的 ...
 


棋盘型DP 棋盘型DP,是DP中比较坑的一种,大多数都可以用深搜AC拿上部分分,剩下的tle2333 所以这个就需要DP,通常我们是从左上朝右下找,当然了,棋盘DP却常常有种暴力的感觉 方格取数 题目链接: [http://codevs.cn/problem/1043/] 输入的方法很简单,也并没有什么复杂的预处理 对于这样一个棋盘,我们很容易想到他的 ...
 


初学DP(4) – 多重背包及其优化 – Codevs 3269
2018年2月11日 / 周日 / 0 条评论

多重背包 我们曾经说过完全背包和01背包,但是这两个方法都有一个问题,就是物件个数都是一致的并且是确定的,但如果他不确定呢? 我们可以定义一个k循环来模拟他的件数,不过显然这样做的华时间复杂度会超过我们的想象 所以我们需要进行优化,优化的方式有两种 二进制优化 单调队列 二进制优化 我们来观察下面这几 ...
 


完全背包 我们先来回顾一下 01 背包 针对于有一定空间,一定数量的物品,每个物品只能放一个,我们可以把他当为 01 背包,它的状态转移方程是: f[j]=max( f [ j – a [ i ] ] + a [ i ] , f [ j ] ) 那么什么是完全背包呢? 针对于有一定空间,一定数量的物品,每个物品能放无数个的背包,我们称其为完全背包, 我们曾经 ...
 


PS:鉴于动态规划的简短性,我会直接放出源代码,不过请不要抄袭,自己写的才能有收获 最长严格上升子队列 题目链接: [ http://codevs.cn/problem/1576/ ] 题目 题目的意图已经很明显了,让我们在一个数组中找出一个最长的从小到大的子序列,想然我们可以对问题进行分化,我是怎么考虑的: 我们可以知道第一个数一定是一 ...
 


DP 动态规划 我们知道,贪心的方法是取全局最优解,而 DP 是指通过解决局部最优解,来找到整个问题的最优解,我们来用看看下面这个求最短路的例子: / 2 \ 1 - 3 - 5 \ 4 / 我们求从 1 到 5 的的最短路,首先我们应该求出 1->2/3/4 的最短路,我们已经知道了 f(1) ( 1 的最短路)=1,将其移动到并算出 1-& ...
 



<