Mrhanice

分类

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

/ 注册

全部文章（共5篇）

Tower of Cubes UVA - 10051

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

dp

2017-08-09

0 479

FatMouse's Speed HDU - 1160

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

dp 最长上升子序列

2017-08-10

0 550

Party at Hali-Bula UVA - 1220

树形DP基础求最大独立集题目描述:老板和员工不能同时选，问最大能选择多少人，并且种种方案是否唯一。解题分析：定义两个数组 int dp[maxn][2];dp[u][1]表示以u为根节点的子树中选择u能得到的最大人数，dp[u][0]表示不选最大人数 int f[ma...

dp 树形DP

2017-08-23

0 490

Perfect Service UVA - 1218

树形DP 题目描述：求最少的服务器，使得其他不是服务器的计算机恰好和一台服务器计算机相邻。解题分析：定义dp[u][0] u是服务器，每个子节点可以使服务器也可以不是。 dp[u][0] = sum(min(dp[v][0],dp[v][1])). dp[u][1]...

dp 树形DP

2017-08-24

0 528

Traveling by Stagecoach POJ - 2686

状态压缩DP 题目描述：旅行商要从a城市到b城市，它共有n张马车票，一共有p条道路，m个城市，每两个城市之间花费的时间是道路之间的距离除以马车的数量，求最小的花费时间。解题分析：关键还是在于怎么表示状态，定义dp[s][v]为票还剩s,现在在城市v所花费的最小时间。那答案就是min...

dp 压缩

2017-08-31

0 515