superzcl

动态规划

ACM2018 and 2019 Exercise(28) ACM模板(23) AIstudy(1) BFS(8) C++学习笔记(20) codeforces(13) DFS(7) hash哈希(2) HDU100题(23) Java 学习笔记(5) KMP(2) Python 学习笔记(8) Python与爬虫(2) sort+结构体(3) STL(25) string(1) web设计(2) 二分和尺取(6) 人工智能学习(1) 位运算(2) 分治和递归(3) 前缀后缀差分打表(2) 博弈论(1) 图论(6) 康托和逆康托展开(1) 排序算法(2) 数学思维题(13) 数论(5) 最小生成树(3) 最短路(2) 未归档(85) 栈和队列(9) 模拟(3) 算法与数据结构(38) 算法与数据结构学习笔记(14) 线段树(5) 贪心(13) 软件安装(7) 速筛与快速幂(5) 面向对象(2)

/ 注册

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

租用游艇问题（动态规划）

问题描述：长江游艇俱乐部在长江上设置了n个游艇出租战1，2，……，n。游客可以在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站 i 到游艇出租站 j 之间的租金位 r(i, j)。试设计一个算法，计算出从游艇出租站1到游艇出租站n所需的最少租金。输入：第一行一个...

2019-10-21

1 2364

HDU2067 小兔的棋盘（DP）

网上看到说这题还能用卡特兰数解，有兴趣的可以取搜搜。题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2067 题意：给出一个矩阵，不能穿越对角线，但可以触碰到，问从a[1][1] 走到 a[n][n]又多少种方法。分析：我们首先考虑a[...

2019-07-30

0 531

HDU2067 小兔的棋盘（DP）

网上看到说这题还能用卡特兰数解，有兴趣的可以取搜搜。题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2067 题意：给出一个矩阵，不能穿越对角线，但可以触碰到，问从a[1][1] 走到 a[n][n]又多少种方法。分析：我们首先考虑a[...

2019-07-30

0 1415

codeforces Round #574(Div.2) Problem-C. Basketball Exercise（DP）

题目链接：http://codeforces.com/contest/1195/problem/C 题意：有两排人每排n个，从左到右为1 - n, 然后从中选出任意个人，但是又一定的规则 1.连续的两个人不能再同一行 2.下一个人的下标一定要比前一个大问能选出来的人的身高...

2019-07-19

0 530

HDU2059 龟兔赛跑（多决策的动态规划）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2059 分析：兔子跑完全部路程的时间是定值，主要看乌龟如何走完全程，且用时最短。用这个最短的时间和兔子的时间相比。首先我们可以把起点和终点都当作充电站，这样一共就有n+2个充电站，特殊情况是起点...

2019-07-18

0 703

简单动态规划-数塔问题变形

寒假前几天有些懈怠，今深刻反思。协会留的作业之一, 虽然一眼就看出了是一个动态规划问题，但是还是因为格式问题困扰好久，主要原因还是自己有些懈怠了做题有些不熟练。要好好反思一下了。问题描述：有 m 颗质量大小不同的石子，从最下面一层开始堆石子，最下面一层放置 n 颗石子，每层减少一颗石...

2019-01-28

0 538

最长递增子序列 51nod 1134

题目：给出长度为N的数组，找出这个数组的最长递增子序列。(递增子序列是指，子序列的元素是递增的）例如：5 1 6 8 2 4 5 10，最长递增子序列是1 2 4 5 10。 Input 第1行：1个数N，N为序列的长度(2 <= N <= 50000) 第2 - N + ...

2018-09-05

0 479

记忆化搜索+树形DP初接触（滑雪）（ Anniversary party）

题目训练网址（密码hpuacm）： https://vjudge.net/contest/245538 其实我之前的博文已经提到过一次记忆化搜索关于01背包的：文章链接对于记忆化搜索其实很好理解。就是每次DFS得到的结果用一个用来记忆值的数组保存。直接来看一道题目更好理解。 ...

2018-08-10

0 841

最大子段和问题

最大子段和 N个整数组成的序列a11,a22,a33,…,ann，求该序列如aii+ai+1i+1+…+ajj的连续子段和的最大值。当所给的整数均为负数时和为0。例如：-2,11,-...

2018-08-07

0 408

动态规划之钱币兑换问题

钱币兑换问题在一个国家仅有1分，2分，3分硬币，将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。 Input 每行只有一个正整数N，N小于32768。 Output ...

动态规划递推

2018-08-07

0 1717