弓长九日

DP

CDQ(1) codeforces(1) SSM框架(3) 《算法竞赛进阶指南》杂谈(14) 二分(1) 分块(1) 动态规划(1) 图论(11) 基本算法(5) 字符串(6) 差分(2) 并查集(2) 思维(18) 搜索(7) 数学(16) 数据结构(17) 未归档(128) 树型结构(4) 树套数(1) 模拟(2) 爬虫(6) 系统配置记录(1) 线段树(8) 计算机网络(2) 贪心(2) 面试(3) 题解(4) 题集(45)

/ 注册

全部文章 / DP （共9篇）

[状压DP] Codeforces Round #585 (Div. 2) E. Marbles

The main fact is that the number of colors is less than 20, which allows us to use exponential solutions. For each pair of colors (i,j), we can calcul...

2019-09-20

0 794

[概率期望DP] 2019 南京网络赛 D.Robot 绿豆蛙的归宿

绿豆蛙的归宿 https://www.luogu.org/problem/P4316 首先这道题是在图上dp的一个标准板子题一般意义上我们需要每个点的转移方程但是这是一个图所以我们考虑拓扑同时每个点连的边数也是需要考虑变成转移系数这样就有了我们算法进阶指南书上代码很好理解但...

2019-09-08

0 723

2019n牛客多校第八场 B Beauty Values (DP or 找规律)

f(i)=f(i-1)+i-(vis[a[i]]?vis[a[i]]:0) 公式怎么出来的呢?考虑由1-i 如果第i个数字出现过,那么他对前一个出现过的i维护的区间是没有贡献的,只有vis[i]-i有贡献. 如果没出现过肯定是前面维护的都+1: 有人可以看出是总ans不断减现在数据之前...

2019-08-19

0 523

2019HDU多校第六场 6635 Nonsense Time (LIS 记录路径)

Problem Description You a given a permutation p1,p2,…,pn of size n. Initially, all elements in p are frozen. There will be n stages that these element...

2019-08-17

0 519

2019HDU杭电多校第三场 HDU 6606 Distribution of books (DP+线段树)

题目要使得最大值最小？考虑二分答案对于每次二分答案（假设为x），如何判定x能否满足分为k份的要求呢？考虑动态规划 dp[i] = max(dp[j]) + 1; (sum[i] - sum[j] <= x) 令dp[i]表示前i个数最多能分成几段, 则如果直接dp，时间复杂度为n^2，显...

2019-08-08

0 495

入门状压DP [SCOI2005] 互不侵犯 [USACO06NOV] 玉米田Corn Fields [NOI2001] 炮兵阵地

先附上 https://blog.csdn.net/qq_40831340/article/details/81502522 TSP问题 Traveling by Stagecoach POJ - 2686 和 2018年小白月赛4 D-郊区春游题解 [SCOI2005]互不侵犯题目描述在N...

2019-05-08

0 763

入门状压DP [SCOI2005] 互不侵犯 [USACO06NOV] 玉米田Corn Fields [NOI2001] 炮兵阵地

先附上 https://blog.csdn.net/qq_40831340/article/details/81502522 TSP问题 Traveling by Stagecoach POJ - 2686 和 2018年小白月赛4 D-郊区春游题解 [SCOI2005]互不侵犯题目描述在N...

2019-05-08

0 688

[区间DP] P1880 [NOI1995] 石子合并 P1063 能量项链

关于区间DP的额外链接 https://blog.csdn.net/qq_40831340/article/details/83478132 北京2014 icpc https://blog.csdn.net/qq_40831340/article/details/82714715 题目石子合并...

2018-11-25

0 619

[博弈] ***游戏 2018-小白月赛-7

B ***游戏链接：https://www.nowcoder.com/acm/contest/190/B 来源：牛客网时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32768K，其他语言65536K 64bit IO Format: %lld 题目描述 Alice和Bo...

2018-09-16

0 511