「組合數學」隔離區

本題是組合數學中的卡特蘭數問題,此處給出了用分治思想推出卡特蘭數遞推公式的分析思路.

我們先來看一下這題的題面.

題面

題目描述

西安發生新冠疫情了，不少人進了隔離區，
隔離區是一個凸多邊形，為了隔離人員的安全，我們需要用木板將隔離區分隔開，為了隔板的穩定，隔板兩邊分別與凸多邊形的頂點相接，當然隔板不能被其他隔板斷開，

凸多邊形是5的情況，有上面5種劃分方案，
現在知道頂點個數，你知道有多少種隔離方案,使得每個區域是三角形？

輸入

一個整數n (3<=n<=20)

輸出

一個整數,即方案數

樣例輸入

5

樣例輸出

5

題目分析與常見錯誤思路

顯然,這是一道卡特蘭數的問題,如果你知道什么是卡特蘭數,那么直接帶卡特蘭數的遞推公式即可解決該問題.

那如果我不知道什么是卡特蘭數,或者沒想到這題是卡特蘭數的問題,又如何解決呢?別急,我們慢慢分析.

就先從n=3的情況開始分析吧.首先很顯然,n=3的多邊形就是三角形,而對于一個三角形,它劃分成三角形的方案數就是1,因為它本身就已經是一個三角形了,無需劃分.

那么n=4呢?這個時候的圖形是個四邊形,簡單分析可以知道,沿著兩條對角線分別可以把它分成兩個三角形,所以這時的劃分方案就是2,如下圖:

那么n=5呢?好像這次沒有之前那么直觀了,不過好在這種情況題面上已經直接給出了:

相信有不少同學經過對上圖的仔細觀察,再加上自己對多邊形劃分的理解,發現5邊形的劃分方式就是分別選擇5個頂點中的一個,然后向不相鄰的頂點連線,所以是5種方案.于是他們由此認為,n邊形的劃分方案也是遵循這個規律的.(你還別說,我第一次做類似的題目的時候,我也是這么想的).

實際上,如果把這種思路提交上去,得到的結果只會是WA.

今天又是陪伴WA的一天呢

其實,我們只要繼續對6邊形的劃分稍加分析,就會找到上述思路的規律的反例,比如下圖這種6邊形的劃分法,顯然是不滿足這個規律的:

正確思路

那正確的規律是什么捏?別急,我們先回到5邊形的劃分中,我們仔細找找有什么潛在的規律.

顯然,對于每種劃分情況,總會存在一個三角形,它總有至少一邊是在原本的五邊形上的,而且這個規律是可以推廣到n邊形的.(不信?如果沒有三角形的邊在n邊形上,那是不是所有三角形都跑到圖形里面去啦?這樣就不是在進行三角形劃分了鴨!嚴格的數學證明這里就略了 才不是我不會證)

所以,我們可以在這個五邊形的5條邊中任意選擇1條邊作為劃分出來的那個三角形的一條邊.由于我們只看劃分的方案,邊的長度是無關緊要的,所以這個五邊形旋轉72°(360°/5)后和原本的圖形可以看成和原本的圖形是同一個圖形(對n邊形自然也成立,因為只需要劃分方案數,顯然這與這個凸n邊形長啥樣無關,所以可以直接把這個n邊形直接看成是正n邊形),因此,無論我們選哪條邊,本質上都是選了同一條邊,所以這里隨便選1條來分析即可.

現在有了一條邊了,距離組成三角形還差一個點.所以我們在剩下來的3個點中可以任意選擇一個點,根據分類加法原理,只需要把選擇每個點的情況所算出來的方案數都加起來,就是最終的答案了.

我們先來看取如下點的情況:

此時三角形選擇完畢后,剩下的左右兩邊是兩個三角形,顯然已經完成了劃分.

接下來看取另一個點的情況:

此時三角形選擇完畢后,剩下的右邊已經沒有圖形了,而左邊是一個四邊形.誒,怎么是四邊形,四邊形怎么辦呢?

別急,我問你,如果我直接給你一個四邊形,我要你劃分成三角形,你會劃分嗎?顯然是可以直接完成的,前面也已經討論過了,是兩種劃分方式.

而在這里,是不是也是同樣的?我們只需要對這個四邊形繼續求劃分方案,是不是就可以啦?也就是,在這里,我們通過選一條邊和一個點劃分出一個三角形,來將問題的規模從原本的5降低到了4.

還有一個點的選取情況與上面類似,最后也是兩種劃分方式,這里就略過了.根據上述分析,我們可以成功求得5邊形的劃分方式是5.

我們再來看看在六邊形中能否做到同樣的事情,我們先選擇這一個點來分解:

此時上面是一個三角形,下面是一個四邊形,我們確實也成功地把問題分小了.接下來只要對下面的四邊形計算有幾種劃分方案即可,上面已經討論過了兩次了,這里不多贅述了.

那如果我們選擇這一個點呢?

顯然,此時問題也一樣變小了,上面已經沒有圖形了,而下面是一個5邊形.啊咧,5邊形怎么辦捏?別急,前面規模降低到4邊形的時候,是不是接著對4邊形進行劃分鴨?那這里我們自然可以一樣地對這個5邊形繼續劃分,怎么劃分捏?前面不是剛剛分析過五邊形的劃分方法嘛.我們可以接著選一條邊,然后通過選點繼續降低規模求解.

分析到這里,此題的思路基本已經有了.我們先固定n邊形的一條邊,然后依次選擇剩下的各個點,這樣劃分后剩下的圖形的邊數就會變小,然后對每一個分小后的部分進行同樣的操作,即繼續進行固定邊、選點來分小,直到問題規模變成可以直接求解的3邊形或4邊形.根據分步乘法原理,此時只需要把劃分出來的左右兩個多邊形的劃分方法數相乘,就是當前選擇的這個點的劃分方法數啦!然后再根據分類加法原理,把每個點的劃分方法數加起來,就是最后的答案啦!

不過這里有個小小的問題,前面的分析中有出現過選擇一個點后,一邊已經沒有圖形的情況.為了和上面統一,我們希望這種情況也可以使用分步乘法原理.為此,我們人為規定此時的劃分方法數為1(此時可以看成"2邊形",所以也就是人為規定"2邊形"的劃分方法數是1),這樣就沒有問題啦!

上述這種思路是一種叫做分而治之,即分治,的思想的應用.我們將大規模問題不斷分解成小規模問題,即減小問題的規模,然后再對每一個小規模問題進行同樣的操作,分成更小規模的問題,即進一步減小問題的規模,如此下去,直到問題被分成小到可以直接解決的規模為止.然后我們便可從這些已經解決的小問題逐步推回,最終解決大問題.快速排序就是典型的分治思想的例子,通過對陣列中的每一段進行小放左、大放右的排序,最終完成對整個陣列的排序.

Nothing is particularly hard if you divide it into small jobs.
如果你能把要做的事情化整為零,就沒有什么事會特別困難，
——Henry Ford(亨利·福特)

代碼撰寫

好了,思路找到了,接下來就來寫代碼吧!

在分治思想中,我們對每個劃分出來的小問題執行的操作和對原本的大問題執行的操作是一樣的,這非常符合遞回的特點,所以我們可以用遞回來解決此問題.

我們先寫一個函式,用來計算劃分數目,區域參考代碼如下:

int f(int n)
{
}

顯然,遞回的基線條件就是3邊形和"2邊形"的情況(4邊形可以通過3邊形和"2邊形"算出來,所以無需列入基線條件.當然,如果你想這么干也可以),此時無需繼續遞回,可以直接回傳值,區域參考代碼如下:

    // 基線條件,3邊形只有一種劃分方式,"2邊形"為了統一,人為規定有一種劃分方式,此時可以直接回傳,結束遞回,開始逐步回傳值計算結果
    if(n == 3 || n == 2)
    {
        return 1;
    }

接下來就是分治的核心代碼了,由于有多種分法,所以我們需要寫一個回圈來分別計算每一種分法的結果數目,然后求和,這個和即為結果.
那這個回圈怎么寫呢?我們觀察一下從最近的點開始選點時的規律:

我們可以發現,右側的多邊形從"2邊形"一直變化到n-1邊形,而左側的多邊形從n-1邊形一直變化到"2邊形",所以我們可以寫一個for回圈,將一側多邊形的邊數作為回圈變數即可.
區域參考代碼如下:

    int res = 0; // 累加器
    for(int i = 2;i < n;i++) // 選點,從最近開始選,一側會從"2邊形"逐步變成n - 1邊形
    {
        // 此處應寫 res += 當前情況的結果數目
    }
    return res; 

那如何計算結果數目捏?如前所述,我們使用分治思想,對劃分出來的兩個部分繼續進行同樣的操作,即進行遞回.然后根據分步乘法計數原理,乘起來就是這種情況的結果數目.

這里可能有些朋友對一側邊數為i時另一側的邊數怎么求感到困惑.當一側是i邊形時,它會用掉多邊形的i - 1條邊(去掉的那1條是中間的那個三角形上的).此時再去掉中間三角形用掉的多邊形上的那1條邊,還剩n - (i - 1) - 1,也就是n - i條邊.再加上中間三角形上的1條邊,那么另一側的多邊形就是n - i + 1條邊啦!

如果還是看不出來,也可以直接利用臨界條件找規律,然后用數學歸納法簡單證明下即可.

區域參考代碼如下:

    res += f(i) * f(n - i + 1); // 對兩個部分進行同樣的操作,不斷把問題分小,直到可以解決

其實,此時我們推出來的這個式子就是卡特蘭數的一種遞推公式,但我們在這里并沒有運用任何和卡特蘭數有關的知識,就已經直接推匯出這個遞推公式了,怎么樣,思維的力量是不是非常強大?(其實卡特蘭數就是從這些問題中抽象出來的一個數列,和斐波那契數列一樣)

這樣這個問題就解決了,這個函式的完整參考代碼如下:

int f(int n)
{
    // 基線條件,3邊形只有一種劃分方式,"2邊形"為了統一,人為規定有一種劃分方式,此時可以直接回傳,結束遞回
    if (n == 3 || n == 2)
    {
        return 1;
    }
    int res = 0;                // 累加器
    for (int i = 2; i < n; i++) // 選點,從最近開始選,一側會從"2邊形"逐步變成n - 1邊形
    {
        res += f(i) * f(n - i + 1); // 對兩個部分進行同樣的操作,不斷把問題分小
    }
    return res;
}

剪枝

由于目前oj的提交通道已經關閉,我不清楚上述的代碼是否會導致TLE(時間超限),但是顯然(如果你顯不出來也沒關系,接著看就好了),上述的代碼實際的運行效率會很慢.因為當我們求f(n)的時候,我們求遍了f(2)到f(n-1),而當我們求f(n-1)的時候,我們再次求遍了f(2)到f(n-2),這里有數量非常可怕的重復運算.

和對求斐波那契數列中出現的重復計算的處理方法一樣,我們也可以通過記憶化搜索的方式來優化掉重復的計算(這種操作稱為對遞回樹進行剪枝).我們引入一個陣列,當我們計算出f(i)(2<=i<=n)的時候,我們就把它存在陣列下標為i的位置上.當我們下一次用到這個f(i)時,我們就直接從陣列中將它取出,不用再繼續遞回下去算了.這樣的一步簡單的優化可以大大提高演算法的效率.

參考代碼如下:

int dp[21]; // 下標0-20,其中0,1,2,3其實是不存資料的.

int f(int n)
{
    // 基線條件,3邊形只有一種劃分方式,"2邊形"為了統一,人為規定有一種劃分方式,此時可以直接回傳,結束遞回
    if (n == 3 || n == 2)
    {
        return 1;
    }
    if (dp[n] != 0) // 當前項已經計算過,直接從陣列中取出,不再繼續遞回
    {
        return dp[n];
    }
    // 此時直接把dp[n]當做累加器即可
    for (int i = 2; i < n; i++) // 選點,從最近開始選,一側會從"2邊形"逐步變成n - 1邊形
    {
        dp[n] += f(i) * f(n - i + 1); // 對兩個部分進行同樣的操作,不斷把問題分小
    }
    return dp[n];
}

當然,這里資料量比較小,如果資料量大起來,還要注意一下是否會出現爆int的問題,必要時將相關資料改成long long.

動態規劃

和斐波那契數列一樣,此處我們還可以進一步優化,將遞回改為遞推,即改為動態規劃.

由于篇幅已經比較長了,并且動態規劃并不是本篇所要討論的主題,所以這里直接給出參考代碼,供感興趣的朋友研究:

#include <stdio.h>

int dp[21];

int main()
{
    int n;
    scanf("%d", &n);
    dp[2] = 1, dp[3] = 1; // 初始狀態定義

    // 狀態轉移
    for (int i = 4; i <= n; i++) // 從4邊形開始遞推,直到n邊形
    {
        for (int k = 2; k < i; k++) // 此回圈同遞回寫法
        {
            dp[i] += dp[k] * dp[i - k + 1];
        }
    }
    printf("%d", dp[n]);
    return 0;
}

參考代碼

下面給出我自己做這道題時候的完整代碼(做的時候記憶化搜索直接過了,就沒有為難自己去寫動態規劃了):

#include <stdio.h>

int dp[21]; // 0-20,其中0,1是不存資料的.

int f(int n)
{
    // 基線條件,3邊形只有一種劃分方式,"2邊形"為了統一人為規定有一種劃分方式,此時可以直接回傳,結束遞回
    if (n == 3 || n == 2)
    {
        return 1;
    }
    if (dp[n] != 0) // 當前項已經計算過,直接從陣列中取出,不再繼續遞回
    {
        return dp[n];
    }
    // 此時直接把dp[n]當做累加器即可
    for (int i = 2; i < n; i++) // 選點,從最近開始選,一側會從"2邊形"逐步變成n - 1邊形
    {
        dp[n] += f(i) * f(n - i + 1); // 對兩個部分進行同樣的操作,不斷把問題分小
    }
    return dp[n];
}

int main()
{
    int n;
    scanf("%d", &n);
    printf("%d\n", f(n));
	return 0;
}

提高

就如開頭所說的那樣,此題其實是一道卡特蘭數的問題.在xcpc勸退樹中,卡特蘭數被歸入基礎中(同樣被歸入基礎里的還有貪心、二分等基礎演算法),所以對于acmer來說,卡特蘭數還是要好好掌握的.

關于卡特蘭數的介紹,這里直接參考維基百科:

卡塔蘭數是組合數學中一個常在各種計數問題中出現的數列，以比利時的數學家歐仁·查理·卡特蘭命名，歷史上，清朝數學家明安圖在其《割圜密率捷法》中最先發明這種計數方式，遠遠早于卡塔蘭，
卡塔蘭數的一般項公式為:

此外,還具有如下兩種遞推公式:

組合數學中有非常多的組合結構可以用卡塔蘭數來計數.比如合法括號組合 二叉樹構成方案 不越過對角線的單調路徑 凸多邊形劃分三角形 進出堆疊的置換 不交叉劃分 填充階梯狀圖形 標準楊氏矩陣數量等.

本題就屬于凸多邊形劃分三角形的典型問題.

關于卡特蘭數在其他問題上的具體應用,可以查看集訓隊的一位大佬整理的博客.

"正是我們每天反復做的事情，最終造就了我們，優秀不是一種行為，而是一種習慣" ---亞里士多德

這里是浙江理工大學22屆ACM集訓隊的成員一枚鴨!

本文首發于博客園，作者：星雙子，除了我自己的轉載請注明原文鏈接：https://www.cnblogs.com/geministar/p/Isolation_zone.html

標籤：其他

上一篇：回溯

下一篇：UE中影片的Retarget基本操作