大连海事大学xcx

动态规划

CodeForces(33) kmp(6) 一通乱写(13) 二分思想(4) 代码待改(4) 区间问题(2) 字符串处理(14) 实用程序(4) 小结论速证(2) 尺取技巧(6) 思维(8) 拓扑排序(4) 排序处理(5) 搜索(45) 数学(4) 数据结构(38) 数论(15) 暴力(2) 最小生成树(8) 最短路径(17) 未归档(33) 树(1) 模拟(10) 比赛后总得写点什么(7) 社团故事(2) 简单作业(19) 算法讲堂附加代码(1) 类模板(2) 线段树(2) 网络流(10) 英语阅读理解(12) 读书笔记(4) 贪心(14) 题解集合(3) 魔板(2)

/ 注册

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

CodeForces - 819B Mister B and PR Shifts（线性dp+思维）

题目大意：现在有一个1~n的全排列，然后定义对于每个数 ai ， disi=|ai−i| ;然后这一串数可以整体向后平移，最后一个跳转到第一个，现在问你如何平移才能使得， ∑ni=1disi 取得最小值。分析： dp[i]表示平移第i步之后，...

2017-09-08

0 415

HDU - 6161 Big binary tree（树上dp+hash优化空间）

题目大意：给你一颗n个节点的完全二叉树，从根节点标号为1。标号为x的节点的左、右儿子标号分别为：2x、2x+1。这棵树的每个节点的权值为它本身的标号。现在告诉你有m次操作，每次操作要么就是把一个点变成给定值，要么就是让你输出经过给定某点的一条最长路径的长度。（一条路径的长度就是它经过的每个点的权...

2017-08-23

0 0

HDU - 6161 Big binary tree（树上dp+hash优化空间）

题目大意：给你一颗n个节点的完全二叉树，从根节点标号为1。标号为x的节点的左、右儿子标号分别为：2x、2x+1。这棵树的每个节点的权值为它本身的标号。现在告诉你有m次操作，每次操作要么就是把一个点变成给定值，要么就是让你输出经过给定某点的一条最长路径的长度。（一条路径的长度就是它经过的每个点的权...

杭电多校赛 acm 算法 hash表树上dp

2017-08-23

0 449

HDU - 6170 Two strings（动态规划）

题目大意：有两个字符串 a、b，a字符串由大写字母和小写字母组成，b字符串除了大写字母和小写字母还有‘ * ’和‘.’。‘.’表示该字符可以变成任意字符，‘ * ’表示该字符的前一个字符可以变成任意多个，包括0个。现在问你，对于给定的两个字符串，是否可以通过对b字符串特殊字符的变换使得a字符串和...

2017-08-23

0 0

HDU - 6170 Two strings（动态规划）

题目大意：有两个字符串 a、b，a字符串由大写字母和小写字母组成，b字符串除了大写字母和小写字母还有‘ * ’和‘.’。‘.’表示该字符可以变成任意字符，‘ * ’表示该字符的前一个字符可以变成任意多个，包括0个。现在问你，对于给定的两个字符串，是否可以通过对b字符串特殊字符的变换使得a字符串和...

2017-08-23

0 355

HDU - 6146 Pokémon GO（表格dp）

题目大意：给你一个2*n的方格，从任意一个格可以到达它周围的任意一个格子（至少有一个角相连接），现在让你从任意一个点开始，不重复地遍历所有格子。问你一共有多少种遍历方法。分析：确定状态： a[i]表示从左上角开始，遍历一个长度为 2*i 的方格，并最终回到左下角的走法数； b[i]...

2017-08-19

0 292

HDU - 6146 Pokémon GO（表格dp）

题目大意：给你一个2*n的方格，从任意一个格可以到达它周围的任意一个格子（至少有一个角相连接），现在让你从任意一个点开始，不重复地遍历所有格子。问你一共有多少种遍历方法。分析：确定状态： a[i]表示从左上角开始，遍历一个长度为 2*i 的方格，并最终回到左下角的走法数； b[i]...

2017-08-19

0 0

CodeForces - 835C Star sky（dp）

题目大意：给你一个 100*100 的地图，然后告诉你这个图中有若干个点有星星，每个星星有一个初始亮度 s ，每个星星的亮度随着时间的变化而周期性变化。现在要进行 1e5 次查询，每次查询给你一个矩阵，和一个时间 t ，让你求 t 时刻该矩阵内每个星星乘他们的亮度的和。注：这里有一个坑点就是...

2017-08-14

0 392

CodeForces - 835C Star sky（dp）

题目大意：给你一个 100*100 的地图，然后告诉你这个图中有若干个点有星星，每个星星有一个初始亮度 s ，每个星星的亮度随着时间的变化而周期性变化。现在要进行 1e5 次查询，每次查询给你一个矩阵，和一个时间 t ，让你求 t 时刻该矩阵内每个星星乘他们的亮度的和。注：这里有一个坑点就是...

codeforces dp 数据结构算法 acm

2017-08-14

0 383

HDU - 6078 Wavel Sequence（动态规划+时间优化）

代码： #include<bits/stdc++.h> #define MOD 998244353 using namespace std; #define MAXN 2050 int dp[MAXN][2] , sum[MAXN][2] , a[MAXN] , b[MAXN]; i...

2017-08-08

0 386