为什么不问问神奇海螺呢

动态规划之基础DP

2018暑假组队赛记录(1) ACM_心情(6) codeforces2018(7) DFS/BFS搜索(10) Linux-Ubuntu(1) python(1) STL(12) 二分搜索(9) 健身(2) 几何之凸包问题(10) 几何之半平面交(6) 几何之旋转卡壳(2) 几何之模拟退火(5) 几何之面积问题(9) 几何技巧(7) 几何问题非模板问题(5) 动态规划之状态压缩(1) 图论之二分图(5) 图论之强联通SCC(5) 图论之网络流(8) 套题(2) 学习(10) 学习资料(28) 年月问题(3) 思维(47) 括号匹配(2) 数学之博弈(6) 数据结构之Manacher(2) 数据结构之单调队列(1) 数据结构之字典树(3) 数据结构之字符串匹配KMP(4) 数据结构之并查集(10) 数据结构之生成树(3) 数据结构之线段树/树状数组(11) 数据结构之莫队算法(1) 数论之Mobius莫比乌斯反演(6) 数论之Nim博弈及变形(2) 数论之伯努利数(1) 数论之佩尔方程(4) 数论之因数相关(1) 数论之数学期望(2) 数论之组合数学(8) 数论之质数相关(1) 数论之进制转换(1) 暴力题(14) 未归档(37) 构造题(3) 模拟(9) 模板集合(打印)(9) 玄学黑科技(1) 生活分享(2) 电影(2) 算法学习(18) 自然溢出(1) 规律(7) 读书(7) 读书笔记(7) 贪心(21) 随机or玄学(1) 高精度(1)

/ 注册

全部文章 / 动态规划之基础DP （共54篇）

免费馅饼 HDU - 1176 【经典DP】

做过的题Σ( ° △ °|||)︴ #include <stdio.h> #include <iostream> #include <string.h> using namespace std; typedef long long ll; const in...

2018-01-23

0 378

codeforces 385d bear and floodlight【状压DP之暴力枚举】

题意：二维坐标xoy . 已知起点(L,0)，终点(R,0)。共有n个路灯，每个路灯坐标(x,y)以及一个角度 sita。路灯的照射范围角的这角度内。问，从L出发到R，最多能走多少米（过程中必须能被光照到）数据分析：1 ≤ n ≤ 20; - 1e5 ≤ l ≤ r ≤ 1e5 100...

2017-08-16

0 474

Codeforces 385C Bear and Prime Numbers【巧妙用埃筛】

题意：已知n个数a[i] 。给定区间[l,r] 。 m次询问，求得在[l,r]区间内的素数中，可以整除a[i]的所有a[i]个数和。例如 2 3 4 5 6区间[2,6] ，素数仅有3,5。可以被3整除的有3、6，可以被5整除的有5.那么累加和是3。数据分析：1 ≤ n ≤ 1e6 :: 2 ≤...

2017-08-14

0 405

838A - Binary Blocks【区间前缀和+思维】

题意：已知n*m的矩阵，由1,0构成，要求确定一个k，使得n*m的矩阵划分成一系列k*k的小矩阵，并且k*k矩阵内的所有值都要相同（要么都为1，要么都为0）。（可以补行或列，补0）思路：遍历k（1~2500），对于每一个k，我们处理出当前k所需要改变的所有次数。首先，我们预处理出(1,1...

2017-08-08

0 387

饭卡 HDU-2546 【01背包变形】

题意:对于饭卡里的余额，如果少于5元，那么不能买任何东西，≥5元，可以买任意一个东西，甚至让饭卡的余额变成负的。现在已知饭卡的余额m，n种菜的价格。思路：最贵的那个肯定最后买，让n-1个菜尽量接近5就可以。 01背包的变形，在n-1个物品中抽取任意个，使得所花的钱尽可能接近m-5。让价值和体...

2017-08-04

0 494

Codeforces Round #427 (Div. 2) C. Star sky

题意：在坐标系上，有n个星星（点），告诉你n个点的坐标，以及它的亮度s，最大亮度c，给定t,左下角坐标，左上角坐标，该矩形区域的星星亮度会变为(s+t)%(c+1)，求该矩形区域所有星星的亮度和。思路：已知所有点，那么我们可以预处理出所有 0,0, –x,y这个矩形区间的每一种亮度对应的数量，...

2017-08-01

0 441

Okabe and El Psy Kongroo CodeForces - 821E【DP+矩阵快速幂】

题意：你从起点(0,0)走到终点(k,0)，其中你每次只可以走右边，右上，右下三个位置，并且有一个附加条件，对于对应的区间，y有个上限。思路：看这题一开始有点像搜索，算算复杂度和实现方法，很麻烦。因为每次你所能到达位置的方案数和前面能到这个点的方案数有关，因此可以用dp做。状态转移方程为...

2017-07-29

0 348

Memory and Scores CodeForces - 712D【好题啊！！】

题意：A和B两个人的初始积分为a,b。每一轮A,B均可从[-k,k]的区间内取出一个数，累加在初始积分上，共执行t轮，问A赢B的有多少种可能。思路：暴力复杂度O(t*kt*k) TLE 。取dp前缀和优化，每次的前缀和为下次的前缀和服务，以此类推。 #include <bits/std...

2017-07-28

0 462

01背包模板、完全背包 and 多重背包（模板）

转载请注明出处：http://blog.csdn.net/u012860063 模版就直接贴代码： 01背包模板： [cpp] view plain copy print ? /* ...

2017-07-05

0 468

【转】背包九讲好好学！

背包九讲目录第一讲 01背包问题第二讲完全背包问题第三讲多重背包问题第四讲混合三种背包问题第五讲二维费用的背包问题第六讲分组的背包问题第七讲有依赖的背包问题第八讲泛化物品第九讲背包问题问法的变化附：USACO中的背包问题 ...

2017-07-04

0 661