Cruiying

分类

2-sat(1) BSGS(2) dfs(2) dp(63) dp + 线段树(1) floyd(3) Hash(1) KM算法(1) Kruskal重构树(2) LCA(6) manachar(2) Mendix(4) tarjan(1) 中位数(1) 主席树(2) 二分(3) 分数规划(3) 前缀和优化dp(2) 单调栈(6) 单调队列(1) 单调队列优化dp(1) 博弈(2) 后缀数组(15) 字典树(1) 差分约束系统(1) 并查集(4) 异或(2) 思维(2) 思维题(4) 扩展欧几里得算法(1) 拉格朗日插值(2) 数论(8) 未归档(15) 构造(1) 枚举(1) 模拟(3) 模板(1) 水题(4) 矩阵加速(2) 线段树(3) 网络流(2) 莫比乌斯反演(2) 莫队(4) 蓝桥杯(1) 规律(2) 贪心(2) 输入输出(1) 题解(1)

/ 注册

全部文章（共51篇）

CF 711C Coloring Trees(三维dp好题)

题意:有n棵树,m种颜色，让你分成k段，数字0代表该树没没有进行染色，需要你从m种颜色中选择一个为其染色，染色的过程中需要消耗代价，求最小代价(已有颜色不必再染色) dp[i][j][k] 表第i个位置颜色为j分为k分的最小代价然后分类讨论：情况1：col[i]和col[i - 1]都存在情况...

dp

2019-07-26

0 489

CF467C (二维dp)

给定一个长度为n的序列，选出k组不重叠且连续的m个数，使其和最大 1<=m*k<=n<=5000（有负数） dp[i][j] 表示前i个数分为j分的最大值转移方程为：dp[i][j] = dp[i - 1][j] + dp[i - m][j - 1] + sum[i] - sum[...

dp

2019-07-25

0 468

CF446A (dp)

问最多修改一个数字，序列可获得地最大严格递增字段长度为多大；维护一个L[i] 数组L[i] 表示第一个a[i] <= a[i - 1] 的位置L[1] = 1; 对于每个位置i #include <bits/stdc++.h> using namespace std; const...

dp

2019-07-25

0 608

CF D. Flowers(dp)

题意:有两种花可以吃，white花只能连续吃k个，red花不受限制，当吃a到b朵花时一共有多少种吃法？注意：(WWWR)不算，因为W(W没有k)个连续 WWR 所以：dp[i]表前i个合法的数量则: dp[i] = dp[i - 1] + dp[i - k]dp[i - 1] 相当于当前位置为R(没...

dp

2019-07-25

0 431

CF106C Buns（多重背包问题）

题意：面包师Lavrenty打算用馅料做几个面包，然后把它们卖掉。Lavrenty有n克面团和m种不同的馅料。馅料种类的下标从1到m，他知道他的第i种馅料剩下ai 克，做一个第i种馅料的面包，恰恰需要bi克的i种馅料和 ci 克的面团，同时这种面包可以卖di 块Tugrik。他也可以做没有馅的面包...

dp

2019-07-24

0 608

CF71C （数学 + dp）

一个圆上有等距的n个顶点，有一些顶点不能选，问是否选取若干点组成一个正多边形.假设可以构成一个正d多边形，首先需要d|n，其次需要有dd个点使得相邻两点距离均为n/d个点枚举n的因子d，以dp[i]表示以i结尾最多可以有几个连续的距离均为d的点，进而有转移方程转移方程：dp[i...

dp

2019-07-24

0 519

CF812B （dp）

题意：有N层楼，每层楼M个房间，每层楼的位置0和M+1代表楼梯，1代表亮着灯，上下楼需要1分钟，房间之间移动需要1分钟，初始位置在左下角，问最少多少分钟能关闭所有灯。 dp[i][0] 表示到达第i层左边楼梯所需要的最少时间dp[1][1] 表示到达第i层右边楼梯所需要的最少时间 L[i] 表示距离...

dp

2019-07-24

0 449

CF913C Party Lemonade

题意是给你n种柠檬水，每种柠檬水有2^（i - 1）次方的体积和c[i]的价格，现在他需要L升，问你最少需要花费多少钱可以买到L升的柠檬水。思路：由于第i瓶的体积为2^(i-1)价格为c[i]，如果我们可以用两瓶第i-1瓶柠檬水体积2^(i-1)所用的价格比它少，我们就用两瓶i-1的柠檬水（以此类...

dp

2019-07-22

0 520

CF607A Chain Reaction

有n个激光塔排成一行，第i个激光塔的位置为ai，威力是bi，当第i个激光塔被激活后，所有在这个激光塔左边且与该激光塔距离小于等于bi的激光塔都会被摧毁，而该激光塔本身不会受到伤害。管理员从右向左依次激活每个激光塔，如果一个激光塔被摧毁了，则它无法被激活。现在管理员想让你帮他一个忙，管理员决定在现有...

dp

2019-07-21

0 407

CF706C Hard problem

考虑到n的范围问题,是10^5次方,那么只能用空间时间为n或者nlogn的方法现在面对一个单词就有两个决策，要么反转它，要么不反转。所以很轻易地就想到了二维dp。用 dp[i][0] 表示不反转第i个单词而且能使1~i这i个单词按照字典序排列的最小消费用 dp[i][0] 表示反转第i个单...

dp

2019-07-21

0 498