Charlesss

ACM_动态规划

ACM_RMQ(2) ACM_二分(5) ACM_二分图(8) ACM_前缀和(1) ACM_干货(6) ACM_并查集(3) ACM_拓扑排序(2) ACM_搜索(24) ACM_最短路(14) ACM_树(1) ACM_树状数组(2) ACM_生成树(8) ACM_线段树(3) ACM_覆盖问题(2) ACM_连通图(2) CodeForces(131) 未归档(172) 第九届蓝桥杯(2) 算法(3) 补题补题补题(55) 题解(3)

/ 注册

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

POJ 3252 Round Numbers(数位dp+前导零)

题目链接：http://poj.org/problem?id=3252 题意是找出l到r范围中的二进制中0的个数大于等于1的有多少个。思路就是我们将它的二进制存起来，然后这里需要判断前导零的情况，不是很难理解，以dp[pos][n0][n1]分别来存第pos位...

2019-01-17

0 588

HDU 3555 Bomb(数位dp入门)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3555 题意是输入一个n，求出1-n中有多少个数不包含49。裸的数位dp。 AC代码： #include <bits/stdc++.h> #de...

2019-01-17

0 552

HDU 2089 不要62(数位dp)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2089 数位dp模板.... AC代码： #include <bits/stdc++.h> using namespace std; int a[10]; int...

2019-01-17

0 616

HDU 6447 YJJ's Salesman(离散化+树状数组+dp)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6447 题意是有一个1e9*1e9的地图，有1e5个村庄，有一个人从(0,0)开始往(1e9,1e9)走，他每次只能向右、向下、向右下走一个单位，当他从一个地方向右下走到一个村庄时(...

2018-08-31

0 505

第十四届华中科技大学程序设计竞赛决赛 F.Beautiful Land(01背包变形)

题目链接：https://www.nowcoder.com/acm/contest/119/F 题意是有T组数据，然后输入n,m，表示有n种树，最大容量是m，然后n行输入每种树的花费和价值，问能得到的最大价值，看一眼数据范围就知道不是简单的裸的01背包了，这种题之前也见过好...

2018-05-14

0 451

牛客小白月赛3 B.躲藏(动态规划)

题目链接：https://www.nowcoder.com/acm/contest/87/B 第一眼看以为是kmp，然后仔细一看是子序列，再看数据范围，暴力的话肯定会超时，所以这道题需要用动态规划来写，令 f[i][j],(j = 1,2,3,4) 表示前 i 个字符中，匹配了字符串...

2018-05-14

0 571

HDU 3746 Cyclic Nacklace(kmp循环节)

题意是给你一个字符串，看它是不是一个由子串循环组成的字符串，比如ababab就是由ab循环组成的，然后让求的是如果这个字符串不是一个循环的字符串就问需要加多少个字符才能变成一个循环的字符串，是的话就为0。用kmp求出字符串前后缀重复数Next[]，则尾部不能循环的部分长...

2018-04-23

0 498

最长回文子序列

和lcs差不多，也可以用递归来写，但是会重复处理很多次，所以还是考虑用动态规划来写。它的动态转移方程为当str[i]==str[j]时，i->j的最长回文子序列就等于，在 i->j 之间上一个最长回文子序列的基础上+2 当st...

2018-03-27

0 692

psd面试(lps或lcs)

题目链接： https://www.nowcoder.com/acm/contest/90/D 题解有两种方法，一种是用另一个字符串把原字符串复制下来并反转，然后对这两个字符串进行LCS，第二种是直接dp。这里我用的是第一种方法。 LPS博客：https:/...

2018-03-26

0 533

最长公共子序列和最长公共子串

首先说一下最长公共子序列和最长公共子串的区别就是前者可以不连续，后者一定是连续的，比如abcde和abced，他的最长公共子序列是abcd或者abce(长度为4)，而他们的最长公共子串只abc(长度为3)。这两个虽然是两个名字，但这都是LCS(Longest Common...

2018-03-26

0 539