大连海事大学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篇）

蓝桥杯算法提高 ADV-277 The Islands（记录转移的简单动态规划）

题目大意：二维平面上有n个点，每个点的坐标是整数，其中有两个特殊点A和B，现在把所有的点按照x坐标从小到大排序，要求一条从起点S到终点T再回到S的最短路径，要求每个点都要经过一次，并且在从S到T的过程中x坐标只能单增，从T回到S过程中x坐标只能单减。A点和B点要分别在去和回来的路上。要计算出最短...

2019-12-26

0 599

CodeForces - 686D Kay and Snowflake（求一棵树的每颗子树的重心）

分析： #include <iostream> #include <vector> #include <algorithm> using namespace std; const int maxn = 1000052; vector <int> u[...

2019-11-06

0 532

HihoCoder - 1362 修补木桶（二分+动态规划+思维技巧）

题目大意：有n个木桶片环形排列高矮不一，有m次机会，每次选择一个长度为L的连续区间将高度变成无限长。数据范围限制： n < ...

2019-11-06

0 478

算法设计与分析：多边形游戏（动态规划）实验报告

实验内容：算法讲解： 1.算法模型引入（区间动态规划）首先，这个问题是一个很经典的区间动态规划问题，我们先看一下什么是区间动态规划：顾名思义，就是动态规划过程中求一个区间的最优解。通过将一个大的区间分为很多个小的区间，求其小区间的解，然后一个一个的组合成一个大的区间而得出最终解，有...

2019-06-21

0 1238

多边形游戏（区间动态规划）

问题：简述：就是一个区间动态规划，为了处理环状结构，一个好的想法是把整个顶点和边的序列在后面再复制一遍。可以比较简化代码实现的复杂度。代码： #include<bits/stdc++.h> using namespace std; const int maxn = 10...

2019-06-01

0 540

ZOJ - 3469 Food Delivery（区间dp）

题目大意：现在一条直线上有n个人，告诉你每个人的位置，现在让你从给定位置出发，经过这n个位置，每个位置有一个对应的不悦值，一开始都为0，第i个位置每过一分钟增加vi的不悦值，现在让你求出经过所有点能得到的最小不悦值为多少。分析：从起始点开始，决策是什么？当然是每一步都有可能去找当前位置左...

2017-09-19

0 305

ZOJ - 3469 Food Delivery（区间dp）

题目大意：现在一条直线上有n个人，告诉你每个人的位置，现在让你从给定位置出发，经过这n个位置，每个位置有一个对应的不悦值，一开始都为0，第i个位置每过一分钟增加vi的不悦值，现在让你求出经过所有点能得到的最小不悦值为多少。分析：从起始点开始，决策是什么？当然是每一步都有可能去找当前位置左...

2017-09-19

0 358

HDU - 6169 Senior PanⅡ（dp+数论）

题目大意：多组测试数据，每组给你三个数：l,r,k;让你输出区间 [ l , r ] 内所有最小不为 1 的因数是 k 的数的和。（l,r,k≤1011）分析：首先，如果 k 不是素数，那么肯定答案是 0 ，此处特判。其次，如果要想，如果 k 和比 k 大...

2017-09-17

0 343

HDU - 6169 Senior PanⅡ（dp+数论）

题目大意：多组测试数据，每组给你三个数：l,r,k;让你输出区间 [ l , r ] 内所有最小不为 1 的因数是 k 的数的和。（l,r,k≤1011）分析：首先，如果 k 不是素数，那么肯定答案是 0 ，此处特判。其次，如果要想，如果 k 和比 k 大...

2017-09-17

0 349

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

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

2017-09-08

0 703