Mrhanice

DP基础

codeforces(2) POJ(8) UVA(14) 云服务器(1) 区间DP(4) 图论(2) 扩展欧几里得(1) 杂谈(2) 树状数组(1) 状态压缩DP(1) 状态空间搜索(1) 简单水题(3) 线段树(4) 背包问题(3)

/ 注册

全部文章 / DP基础（共3篇）

FatMouse's Speed HDU - 1160

最长上升子序列 + 打印路径题目描述：找最长的老鼠序列要求，后面的老鼠体重比前面的打，速度比前面的小，求这个最长序列的长度，并输出老鼠序列。解题分析：此题需要排序，之后按照最长上升子序列并打印路径就行了。代码如下： #include <iostream> #...

dp 最长上升子序列

2017-08-10

0 550

Wavio Sequence UVA - 10534

最长上升子序列题目描述：给了一个定义的序列Wavio，该序列的定义是：长度为2*n + 1，前n+1个数是严格递增的，后n+1个数是严格递减的，且相邻两个数不重复。求最长的Wavio序列的长度。解题分析：数据量是10000，显然n*n的算法行不通,必须得用n*logn的算法。在本...

2017-08-09

0 647

Tower of Cubes UVA - 10051

类似于最长上升子序列题目描述：要求把给出的小正方体尽量排得更高，要求是：下面的小正方体的重量要大于上面小正方体的重量，且相邻的正方体上面的地面要和下面的顶面颜色相同，求最大高度，并打印小正方体的排放，依次从上到下打印小正方体的序号和那个面朝上。解题分析：刚学了最长上升子序列，听说...

dp

2017-08-09

0 479