动态规划

[NOI2009]诗人小G

题目描述

小G是一个出色的诗人,经常作诗自娱自乐。但是,他一直被一件事情所困扰,那就是诗的排版问题。 一首诗包含了若干个句子,对于一些连续的短句,可以将它们用空格隔开并放在一行中,注意一行中可以放的句子数目是没有限制的。小G给每首诗定义了一个行标准长度(行的长度为一行中符号的总个数),他希望排版后每行的长度都和行标准长度相差不远。显然排版时,不应改变原有的句子顺序,并且小G不允许把一个句子分在两行或者更多的行内。在满足上面两个条件的情况下,小G对于排版中的每行定义了一个不协调度, 为这行的实际长度与行标准长度差值绝对值的P次方,而一个排版的不协调度为所有行不协调度的总和。 小G最近又作了几首诗,现在请你对这首诗进行排版,使得排版后的诗尽量协调(即不协调度尽量小),并把排版的结果告诉他。 (更多…)

DefFrancis
动态规划

[BalticOI 2016 Day2]城市

题目描述

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

DefFrancis
动态规划

WJMZBMR打osu! / Easy

题目描述

某一天WJMZBMR在打osu~~~但是他太弱逼了,有些地方完全靠运气:( 我们来简化一下这个游戏的规则有 次点击要做,成功了就是o,失败了就是x,分数是按combo计算的,连续 个combo就有 分,combo就是极大的连续o。 Sevenkplus闲的慌就看他打了一盘,有些地方跟运气无关要么是o要么是x,有些地方o或者x各有50%的可能性,用?号来表示。 比如oo?xx就是一个可能的输入。 那么WJMZBMR这场osu的期望得分是多少呢? 比如oo?xx的话,?o的话就是oooxx => 9,是x的话就是ooxxx => 4 期望自然就是 (更多…)

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