beckyUp

动态规划

--------------作业---------------(4) ACM算法(15) c++(16) codeforces(8) CSP(2) fft(1) java(8) java图像(1) KMP(4) tcp/ip(4) 二分(5) 二分图匹配(1) 分块(1) 分治(2) 前缀和(2) 区间dp(3) 博弈(2) 后缀数组(1) 图论(8) 字典树(1) 字符串(8) 小技巧(9) 并查集(2) 感悟(13) 操作系统(2) 数据库(3) 数据结构(22) 数论(10) 未归档(7) 构造(2) 树形dp(1) 水题(22) 状压dp(2) 脑洞(1) 自然语言处理(2) 计算几何(5) 计算方法(4) 读书笔记(2)

/ 注册

全部文章 / 动态规划（共18篇）

黑客的攻击 uva 11825【dp+枚举】

蓝书经典例题题目大意将一堆集合分组，使得每个组的并集等于全集，问最多有个多少个这样的集合题目分析 n很小，所以用二进制来存储集合 cover[s] 记录 s中所包含的几个集合的并集 f[s] 记录能划分成的集合个数 f[s]=max{f[s-s0] s0 是s的子集，且cover[s...

2019-04-09

0 475

约瑟夫环变形问题LA 3882

约瑟夫环不再赘述对于约瑟夫环变形问题当问题规模变大，我们只考虑最后被删除的那个人假设从0开始报数他在最后一次，只剩自己的时候，报数为0 记 dp[1]=0; 倒数第二次，还剩下两个人，所以这个人这一轮的序号应该是 (dp[1]+k)%2 倒数第三轮此人序号应为 dp[3] = (dp...

2019-04-08

0 493

最优排序二叉树问题OBST【区间dp+四边形不等式优化】

题目大意给定n个点的权值，要求构建一棵二叉搜索树，使得他满足 ,权值乘以深度的和最小题目分析这个题目，我们通过BST的构建，由于BST 的性质可知，根节点的左边一定小于根，右边一定大于根，所以先对所有数据排序，然后枚举根节点。根节点对于答案的贡献 fk*1，由于第k个结点作为根节点了，因...

2019-04-01

0 903

uva 10306 e-coins【dp】

二维完全背包 #include <bits/stdc++.h> #define cl(a) memset(a,0,sizeof(a)) #define rep(i,a,b) for(int i=a;i<=b;i++) #define per(i,a,b) for(int i=b;...

2019-02-26

0 530

hdu 2089 不要62[数位dp入门]

又一次开始搞数位dp了，一直在拖，希望这次能够彻底学会 #include <bits/stdc++.h> using namespace std; typedef long long ll; int a[20]; ll dp[20][2];//不同的题目状态不同 ll dfs(int...

数位dp

2018-08-21

0 418

ccpc wannafly 秦皇岛E kingdom【树形dp】【已修正】

这个题目是一个树形dp ，我们记F[i] 为总数为i的时候的结果， g[i][j] 表示的总数为i ，心腹的子树结点为j的情况所以，根据背包 g[i][j] = max(g[i][j-1],g[i-j][j]+f[j]) 第一种情况就是多出的一个结点接在左边，那么这个节点作为心腹的话，就不会有...

2018-08-21

0 413

字符串的扩展距离问题

题目描述：对于长度相同的2个字符串A和B，其距离定义为相应位置字符距离之和。2个非空格字符的距离是它们的ASCII码之差的绝对值；空格与空格的距离为0，空格与其他字符的距离为一个定值k。在一般情况下，字符串A和B的长度不一定相同。字符串A的扩展是在A中插入若干空格字符所产生的字符串。在字符串A和B的...

2018-04-18

0 796

埃森哲杯第十六届上海大学程序设计联赛春季赛暨上海高校金马五校赛L

K序列链接：https://www.nowcoder.com/acm/contest/91/L 来源：牛客网题目描述给一个数组 a，长度为 n，若某个子序列中的和为 K 的倍数，那么这个序列被称为“K 序列”。现在要你对数组 a 求出最长的子序列的长度，满足这个序列是 K 序列。 ...

2018-04-15

0 586

hdu 1284 钱币兑换【完全背包问题】

题目大意，给你1分、2分、3分的硬币，问你组成n分的钱有多少种兑换方法这个题就是一个不带价值的完全背包问题，由于和完全背包问题的模型还是有一点差距，那么我们来讲讲如何把它作为一个完全背包问题来分析。首先这个题， 1,2,3分的硬币数量是无限的，那么对于总量为j的硬币来说，他可以取k1个1分的，...

2018-03-27

0 463

51nod 1277 B - 字符串中的最大值【KMP+dp】

题目描述：给你一个1e5长度的字符串，问每个字符串在其中出现的次数，求次数乘以长度的最大分析：这个题一开始就想着要统计每个前缀出现的次数是比较麻烦的，因为字符串的长度太长，时间复杂度远远不够，但是仔细观察，由于都是前缀，所以，我们可以发现，前缀的前缀一定在前缀中重复出现，这句话可能不好理解，举个例...

2018-03-27

0 463