动态规划

[BalticOI 2016 Day2]城市

题目描述

在 Byteland 有  个城市,并且其中有  个国王经常来访的主要城市。 其中有  条道路,每条道路连接两个城市。然而不幸的是,这些道路的环境极差使得国王无法全速驶过。 对于每条道路,翻修的成本是已知的。你的任务是选择性的翻修道路使得  个主要城市都可以经过翻修后的道路互相连通,且总成本尽量小。 (更多…)

DefFrancis
动态规划

[USACO08NOV]奶牛混合起来Mixed Up Cows

题目描述

约翰家有N头奶牛,第i头奶牛的编号是Si,每头奶牛的编号都是唯一的。这些奶牛最近 在闹脾气,为表达不满的情绪,她们在挤奶的时候一定要排成混乱的队伍。在一只混乱的队 伍中,相邻奶牛的编号之差均超过K。比如当K = 1时,1, 3, 5, 2, 6, 4就是一支混乱的队伍, 而1, 3, 6, 5, 2, 4不是,因为6和5只差1。请数一数,有多少种队形是混乱的呢? (更多…)

DefFrancis
动态规划

[USACO06NOV]玉米田Corn Fields

题目描述

农场主John新买了一块长方形的新牧场,这块牧场被划分成M行N列(1 ≤ M ≤ 12; 1 ≤ N ≤ 12),每一格都是一块正方形的土地。John打算在牧场上的某几格里种上美味的草,供他的奶牛们享用。 遗憾的是,有些土地相当贫瘠,不能用来种草。并且,奶牛们喜欢独占一块草地的感觉,于是John不会选择两块相邻的土地,也就是说,没有哪两块草地有公共边。 John想知道,如果不考虑草地的总块数,那么,一共有多少种种植方案可供他选择?(当然,把新牧场完全荒废也是一种方案) (更多…)

DefFrancis
题解

[ZJOI2006]物流运输

题目描述

物流公司要把一批货物从码头A运到码头B。由于货物量比较大,需要n天才能运完。货物运输过程中一般要转停好几个码头。物流公司通常会设计一条固定的运输路线,以便对整个运输过程实施严格的管理和跟踪。由于各种因素的存在,有的时候某个码头会无法装卸货物。这时候就必须修改运输路线,让货物能够按时到达目的地。但是修改路线是—件十分麻烦的事情,会带来额外的成本。因此物流公司希望能够订一个n天的运输计划,使得总成本尽可能地小。 (更多…)

DefFrancis