Mrhanice

分类

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

/ 注册

全部文章（共50篇）

HDU 1540 Tunnel Warfare

线段树单点更新区间合并题目描述：一串线性的村庄，除了头尾的两个村庄，其他村庄都和左右的两个村庄相邻，可以摧毁一个村庄，这样连接的关系就会被破坏，也可以修复一个村庄，连接的关系也会修复，询问一个村庄，求与它相连接的村庄有多少个。解题分析：借鉴了kuangbin的想法，维护一个节点...

线段树

2017-09-20

0 532

Traveling by Stagecoach POJ - 2686

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

dp 压缩

2017-08-31

0 515

XYZZY HDU - 1317

Floyd判断连通性 + spfa判断正环。题目描述：有一百个房间，你的初始能量值是100，从起点1开始出发，判断你能不能到达第100个房间。不能到达的情况是，在中途的过程中生命值降为0及以下，或者是没有路能够到达房间100。注意：题目中是单项边。而且同一个房间可以进入多次。解题...

2017-08-29

0 489

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

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

FatMouse's Speed HDU - 1160

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

dp 最长上升子序列

2017-08-10

0 550

SuperSale UVA - 10130

01背包题目描述：一家人去超市买东西，各种物品有价格和重量，每个人都有自己的背包容量，求这一家人能够获得最大价值。解题分析：刚开始被这题给唬住了，想成了如果一个物品被某人买了，则其他人不可以卖这个物品，那这就难了。但是想想也该明白那家超市一种物品只卖一件啊，超时的物品是任意多的。...

2017-08-10

0 653

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

The trouble of Xiaoqian HDU - 3591

多重背包 + 完全背包题目描述：xiaoqian需要买T钱的货物，他有n种不同面值的硬币，每种硬币是有限个。他给收银员钱，收银员找给他钱（如果需要找钱的话），收银员总是给他最少的硬币数目。求xianqian最少需要接触多少硬币（他给收银员的，收银员给他的）。解题分析：可以分别计算...

2017-08-07

0 563