2016 UESTC Training for Dynamic Programming H – 柱爷大战滑稽王 LCS转LIS
H - 柱爷大战滑稽王 LCS转LIS Source 2016 UESTC Training for Dynamic Programming My Solution 首先直接用LCS做必定会TLE LCS 转 LIS O(m*n) ==> O(nlogn) 然后根据Ai来进行映射，因为B虽然有重复的，…
Codeforces Round #420 (Div. 2) E. Okabe and El Psy Kongroo dp+矩阵快速幂
E. Okabe and El Psy Kongroo dp+矩阵快速幂 My Solution 题意：从(0,0)走到(k,0)(1 ≤ k ≤ 1e18)，每次可以从(x, y) 走到 (x+1, y+1) 或 (x+1, y) 或 (x+1, y-1)，然后必须在很多个y == ci的线段下面走， (…
UVALive – 7544 Banking II 朴素dp、类似于背包的dp
7544 Banking II 朴素dp、类似于背包的dp Source UVALive - 7544 My Solution 题意：给出一个数字字符串，然后给出一个由小写字母构成的字符串，每个小写字母x 表示 有且必须选择一段连续的长度为 x - 'a' +…
2016 ACM/ICPC Asia Regional Shenyang Online 1009 QSC and Master 区间dp
QSC and Master 区间dp Source 2016 ACM/ICPC Asia Regional Shenyang Online My Solution 状态定义： dp[i][j][u] u == 1 时表示 当端点 i， j 进行合并时(取出 val[i] 、 val[j] 时) 或 i < k < k…
UESTC 1692 这是一道比CCCC简单题更有想象力的中档题 完全背包
这是一道比CCCC简单题更有想象力的中档题 完全背包 Source 2017 UESTC Training for Dynamic Programming UESTC 1692 这是一道比CCCC简单题更有想象力的中档题 My Solution 完全背包 dp[i][j][k]，已经考虑…
UESTC 1691 这是一道比CCCC简单题经典的中档题 多重背包
这是一道比CCCC简单题经典的中档题 多重背包 Source 2017 UESTC Training for Dynamic Programming UESTC 1691 这是一道比CCCC简单题经典的中档题 My Solution 多重背包 转化成0-1背包来跑。 for(i = 1; i <= n;…
UESTC 1606 难喝的饮料 0-1背包+完全背包
难喝的饮料 0-1背包+完全背包 Source 2017 UESTC Training for Dynamic Programming UESTC 1606 难喝的饮料 My Solution 0-1背包+完全背包 通过递推顺序，第一维可以直接省略 for(i = 1; i <= n; i++){ if(c[i])…
HDU – 2825 Wireless Password AC自动机+状压dp
Wireless Password AC自动机+状压dp Source HDU - 2825 My Solution 题意：给出一个字符串集合，集合里包含m(m <= 10)个长度不大于10的字符串，要求构造长度为n(1<=n<=25)的字符串且子串中至少出现k个集合…
Gym – 101102A A. Coins 背包问题、数学
A. Coins 背包问题、数学 Source 2016 ACM Amman Collegiate Programming Contest UESTC 2017 Winter Training #1 Gym - 101102A My Solution 题意：在a中选一个子集b中选一个子集，使它们的和为w且abs(s…
HihoCoder – 1037 数字三角形 基础dp、朴素dp
数字三角形 基础dp、朴素dp Source HihoCoder - 1037 My Solution 题意：dp基础题，给出一个数字三角形，求一条从顶到底的路径，路径权值和的最大值。 基础dp、朴素dp 复习下dp基础知识， 动态规划的…
URAL – 1158 Censored! AC自动机+dp
Censored! AC自动机+dp Source URAL - 1158 ACM ICPC 2001. Northeastern European Region, Northern Subregion My Solution 题意：给出n个不同的字符，用这n个字符构成长度为m的字符串，要求每个串的子串都不出现…
Gym – 100507G G. The Debut Album 数位dp+内存优化
G - The Debut Album 数位dp+内存优化 Source Gym - 100507G ACM ICPC 2014-2015. NEERC. Eastern Subregional Contest Yekaterinburg, October 11, 2014 My Solution 题意：最多连续a个1，最多连续b个2，…
Good Bye 2016 D. New Year and Fireworks dp+枚举、状态总数
D. New Year and Fireworks dp+枚举、状态总数 My Sution 题意：烟花刚开始时占用一个格子的空间，然后开始移动经过ti秒(每秒移动一个格子)，开始分裂，分裂成2半，分别向2边偏移了45度，然后运动ti秒，总共n个ti…
Codeforces Round #383 (Div. 2) D. Arpa’s weak amphitheater and Mehrdad’s valuable Hoses 并查集+双重01背包
D. Arpa's weak amphitheater and Mehrdad's valuable Hoses 并查集+双重01背包 My Soluton 题意：一堆人，这些人构成一些集合，2个元素至少有一条路径则为同一个集合，对于这些集合每个交合要么全取要不去不超过…
HDU 5904 LCIS __ dp、LCIS
LCIS dp Source BestCoder Round #87 My Solution dp、LCIS、 最长公共上升子序列且每次递增 1 状态定义：dpa[i] 表示以ai结尾的每次递增 1 的 LIS 的最大长度， dpb[j] 表示以bi结尾…
Codeforces Round #371 (Div. 2) C. Sonya and Queries 压位、二进制来状态压缩
C. Sonya and Queries 压位、二进制来状态压缩 Source Codeforces Round #371 (Div. 2) My Solution 压位、二进制来状态压缩 根据 ai的各个digit的奇偶可以把它状态压缩到一个 Ind 比如 Ind = 0； 然后最…
Codeforces Round #369 (Div. 2) C. Coloring Trees 数位dp，好题
C. Coloring Trees 数位dp，好题 Source Codeforces Round #369 (Div. 2) My Solution 数位dp， 好题 状态定义 dp i j k 为 当前在 从左往右 第 i 位， 且 以 j 结尾， 已经有 k 个片段 初始化 dp[ i ][…
UESTC 2016 Summer Training #2 Div.2 A dp、递推、多阶段问题
A - A dp、递推、多阶段问题 Source http://acm.hust.edu.cn/vjudge/contest/view.action?cid=121703#problem/A My Solution 训练的时候刚开始想到的是记忆化搜索， 但无论怎么优化还是TLE 3，没办法，想…
2016 UESTC Training for Dynamic Programming L – 柱爷抢银行MkⅣ dp 线段树优化
L - 柱爷抢银行MkⅣ dp 线段树优化 Source 2016 UESTC Training for Dynamic Programming My Solution dp 线段树优化 dp[i] = max(dp[j]) + v[i] // x[i] – y[i] <= x[j] < x[i] 首先按x[i]升序排序 …
2016 UESTC Training for Dynamic Programming D – 柱爷的恋爱 区间dp、记忆化搜索
D - 柱爷的恋爱 区间dp、记忆化搜索 Source 2016 UESTC Training for Dynamic Programming My Solution 记忆化搜索 dp[a, b] 表示 [a, b) 内的方案数； 如果line[a] 要去掉， 则直接转移 dp[a, b] = dfs(a…
