Day24h

动态规划

2019 Multi-University Training(2) 2019牛客暑期多校训练营(1) CF(37) Record My Feelings(5) 图论(4) 字符串(3) 数学(20) 数据结构(8) 未归档(5) 模板(23)

/ 注册

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

背包问题

背包问题当范围很小的背包问题是很容易解决的，而当范围很大\((例如：1\le n\le 100,1\le w_i\le10^7,1\le v_i\le 100,1\le W\le 10^9)\)时，就应该换一种 dp 的表示方式，这样才能够降低其复杂度。 \(dp[i+1][j...

dp

2020-01-14

0 390

完全背包问题

完全背包问题 \(\begin{cases}dp[0][j]=0\\dp[i+1][j]=max(dp[i][j-k*w[i]]+k*v[i]) \end{cases}\) 代码： int n,W; cin >> n >> W; for(int i=0;...

dp

2020-01-14

0 561

最长公共子序列

最长公共子序列注：子序列是可以不连续的。递推公式： \(dp[i+1][j+1]=\begin{cases}dp[i][j]+1&(s_{i+1}=t_{j+1})\\max(dp[i][j+1],dp[i+1][j])&(其他)\end{cases}\...

字符串 dp

2020-01-14

0 398

K for the Price of One

B. K for the Price of One (Hard Version) 赛时失手推错了规律... 这个题不是单调递增的但是它有一个规律：当买同样多的东西时，优先买便宜的所以我们可以求出买 i 个东西时最便宜的价格 sort(a+1,a+n+1); for...

思维 dp

2020-01-14

0 394

Dr. Evil Underscores

D - Dr. Evil Underscores 参考：Codeforces Round #613 (Div. 2) Editorial 其实比赛的时候就已经想到了基本上一样的解法，可是最后还是没有写出来... 具体思路就是分治，在二进制中，如果\(a_1{\sim}a_n\)...

分治

2020-01-11

0 480

Garland

C - Garland 参考：Codeforces Round #612 (Div. 2) A~E2 题解试了试暴力的方法，感觉不大行，所以转战dp 总共有四个状态\(dp[x][i][j][bj]\)，表示还有 i 个奇数，j 个偶数可以使用，x~n 位置的复杂度之和的最小值，且位...

dp

2020-01-08

0 452

不要62

不要62 参考： HDU2089 不要62 标准数位DP 从最高位开始递归，如果有4或者62则不往下走。 dp[i][j]表示的是有i位数字，且第i位数字为j并满足题给条件的数字的个数其实也就是记忆化搜索的感觉，保留搜过的状态，以避免重复运算。代码： //...

数位DP dp

2019-11-09

0 416

windy数

windy数参考：题解 P2657 【[SCOI2009]windy数 windy数数位dp练习题——只要学了数位dp就异常简单的题用数位dp解决这个问题。数位 DP 问题往往都是这样的题型，给定一个闭区间[l,r]，让你求这个区间中满足某种条件的数的总...

数位DP dp

2019-11-09

0 392

Yet Another Division Into Teams

E. Yet Another Division Into Teams 首先要想明白一个东西，就是当一个小组达到六个人的时候，它一定可以拆分成两个更优的小组。这个题可以用动态规划来写，用一个数组来保存状态，用一个队列来尝试新的状态，但是因为上面的这个特性，每一次只会有三个新的状态。 ...

dp

2019-11-07

0 453

Common Subsequence

L - Common Subsequence 参考：ACM POJ 1458 Common Subsequence (最长公共子序列，动态规划）思路：二维动态规划。 dp[i][j]：在截止至s1的i-1，s2的j-1位置，两个串的最长公共子序列长度。动态规划方程： ...

最长公共子序列 dp

2019-11-05

0 355