标签归档:记忆化搜索

[bzoj 1055][HAOI2008] 玩具取名

Description

  某人有一套玩具,并想法给玩具命名。首先他选择WING四个字母中的任意一个字母作为玩具的基本名字。然后他会根据自己的喜好,将名字中任意一个字母用“WING”中任意两个字母代替,使得自己的名字能够扩充得很长。现在,他想请你猜猜某一个很长的名字,最初可能是由哪几个字母变形过来的。

继续阅读

[bzoj 1048][HAOI2007]分割矩阵

Description

  将一个a*b的数字矩阵进行如下分割:将原矩阵沿某一条直线分割成两个矩阵,再将生成的两个矩阵继续如此分割(当然也可以只分割其中的一个),这样分割了(n-1)次后,原矩阵被分割成了n个矩阵。(每次分割都只能沿着数字间的缝隙进行)原矩阵中每一位置上有一个分值,一个矩阵的总分为其所含各位置上分值之和。现在需要把矩阵按上述规则分割成n个矩阵,并使各矩阵总分的均方差最小。请编程对给出的矩阵及n,求出均方差的最小值

继续阅读

AIO2006 Solution

Fashion Statement

In the latest trend of skin-tight jeans and slimline handbags, having a bulging wallet or purse is simply a fashion crime. You are faced with a dilemma: either you find yourself disowned by your fashion-conscious friends, or risk carrying too little money for your taxi ride home.

You wish to carry the exact amount of money for your taxi ride (in case you are mugged or otherwise lose it). However, you also wish to use as few notes as possible to avoid being ridiculed by your friends. The notes available to you come in denominations of $1, $5, $20 and $100 (you never carry coins, which are simply far too bulky).

For example, if your taxi fare costs $67, the smallest number of notes you can carry is six — this is achieved by carrying three $20 notes, one $5 note and two $1 notes (20+20+20+5+1+1 = 67).

Your task is to determine the smallest number of notes you need to carry in order to make up a given taxi fare.

继续阅读

AIO2008 Solution

Ladybugs

You really like ladybugs. This is fortunate, as dozens of ladybugs have recently taken up residence in your garden. Every day they emerge into the sunlight and climb your garden fence. The fence is a series of regularly spaced posts which gleam brightly in the sun. The ladybugs settle into their favourite resting spots atop these posts.

\includegraphics[width=12cm]{ladybug}

Winter is nigh and you wish to protect the ladybugs from the rain. You set out to construct a rain shelter using a single length of ribbon propped up with toothpicks. To protect all the ladybugs, the ribbon must be long enough to cover all their favourite resting spots. Ribbon is not cheap, so you wish to use the shortest length of ribbon you possibly can. A ribbon of length k will cover precisely k adjacent fence posts.

For example, on the fence in the diagram above there are two ladybugs sitting on fence post 3 and one ladybug on each of 2, 6, 7 and 9. The ribbon rain shelter must cover all the posts from 2 through to 9 inclusive, so the shortest possible length of ribbon that covers all the ladybugs is 8.

Your task is to write a program to calculate the minimum length of ribbon that will cover all the ladybugs.

继续阅读