1、問題求解與程序設(shè)計(jì)第七講 內(nèi)容提要 搜索 討論 1011 stick 討論 1054 the troublesome frog 參考王知昆的冬令營報(bào)告 作業(yè)搜索的普通概念 在解空間中嘗試一切能夠，找出滿足條件的取值 回想填數(shù)游戲：1-9填在3*3的表格中，使得行、列、對角線的和均為15。 方程組 搜索 逐一嘗試+剪枝標(biāo)題討論 1011 stick標(biāo)題討論 The Troublesome Frog IOI 2002 day 1 task 1問題 稻田問題 青蛙從外面跳入稻田，踩過一些禾苗，后，跳出稻田。問題 蛙路：一個方向，等間距，大于等于3個點(diǎn) 不同蛙路：可以方向不同，間距不同問題 許多青蛙跳

2、過稻田，構(gòu)成多條蛙路，不同蛙路可以踩過同一作物。問題 青蛙每天早上踩壞稻田，早上人們發(fā)現(xiàn)稻田有假設(shè)干株作物被踩壞，但不知多少青蛙來過。也有不在蛙路上的被踩壞的作物。問題 問，給定一塊被踩壞的稻田，求能夠的最長的蛙路上被踩壞的作物的數(shù)目。輸入 第一行整數(shù)R和C，稻田的行數(shù)和列數(shù) 第二行整數(shù)N，表示被踩壞的作物總數(shù)。 后續(xù)N行，每行兩個整數(shù)i,j為被踩壞的作物的行和列的位置:1=i=R,1，1=j=C。 每個被踩壞的作物只出現(xiàn)一次。輸出 單個整數(shù)- 表示最長能夠蛙路上踩壞的作物數(shù)目樣例 Figure- 4問題的解 這道標(biāo)題也就是說，在給出的n個點(diǎn)中找出一些點(diǎn)的序列來，使得每一個點(diǎn)相對于上一個點(diǎn)的坐

3、標(biāo)都是一個一樣的向量，且第一個點(diǎn)減去這個向量和最后一個點(diǎn)加上這個向量后均落在方格的外面。 問題的解 我們先對這些點(diǎn)按照坐標(biāo)排序。然后依次循環(huán)出要求的序列中的第一個和第二個點(diǎn)，這樣我們就知道后一個點(diǎn)相對于前一個點(diǎn)的坐標(biāo)是多少了。然后我們依次用第二個點(diǎn)加上這個坐標(biāo)的出第三個點(diǎn)，第三個點(diǎn)加上這個坐標(biāo)得出第四個點(diǎn)等等。當(dāng)然，我們還需求判別一下這求出來的第三個、第四個點(diǎn)能否在給定的點(diǎn)內(nèi)。 問題的解 由于每個點(diǎn)的上一個點(diǎn)/下一個點(diǎn)最多只能有n種選擇，故一個點(diǎn)最多屬于n條不同的蛙路。這樣，對于某個確定的點(diǎn)來說，它的一切能夠的下一個需求判別的點(diǎn)至多有n個。這樣由于判別一個點(diǎn)在不在給定的點(diǎn)內(nèi)只需求O(1)的復(fù)雜

4、度，所以我們只需求O(n2)的時間就可以得出問題的解答。由于這個算法需求一個r*c的表來保管點(diǎn)在方格中的存在形狀，故空間復(fù)雜度為O(n2)。 問題的解 需求留意的是，蛙路中的點(diǎn)數(shù)少于3個的時候是不思索的。所以這個時候的蛙路中的點(diǎn)數(shù)應(yīng)該按照0來算。 實(shí)現(xiàn)細(xì)節(jié) Frog vs frog 平面上點(diǎn)的表示 Frog 2 0 有冗余代碼 Frog 2 1 去掉冗余 Frog 2 2 compare 判別 Frog 2 3改動表達(dá)式寫法 Frog 2 4添加剪枝 Frog 2 5不太好的剪枝順序 Frog 2 6較好的剪枝順序測試數(shù)據(jù)No. N, (R*C) Description Solution1 1

5、8, (6 * 7) Sample data in the task description 42 10, (10 * 10) Manually designed 53 25, (50 * 50) Manually designed 134 50, (10 * 10) Several Lines + random points 105 100, (20 * 20) modified random point set 106 300, (30 * 30) modified random point set 157 500, (55 * 55) Several Lines + random poi

6、nts 288 500, (100 * 100) Special case for no solution 09 1000, (100 * 100) Several Lines + random points 3410 1000, (1000 * 1000) Several Lines + random points 25011 2000, (50 * 50) Random (uniform) points 2512 2000, (100 * 200) Several Lines + random points 3313 2000, (1000 * 2000) Several Lines +

7、random points 333測試數(shù)據(jù)14 3000, (60 * 60) Uniformly random points 3115 3000, (500 * 500) X shapes and random points 50016 3000, (5000 * 1) Horizontal line 2017 3000, (5 * 1000) Several Lines + random points 1718 4000, (100 * 100) Random points (uniformly) 3419 4000, (200 * 20) Very dense points set 20020 4000, (1000 * 1000) Several Lines + random points 50021 4000, (5000 * 5000) Several Lines + random points 31122 5000, (100 * 100) Chess board style 10023 5000, (1000 * 1000) Several Lines + random points 33424 5000