一個監(jiān)獄里有P個并排著的牢房，從左往右一次編號為1,2,…,P。最初所有牢房里面都住著一個囚犯?，F(xiàn)在要釋放一些囚犯。如果釋放某個牢房里的囚犯，必須要賄賂兩邊所有的囚犯一個金幣，直到監(jiān)獄的兩端或者空牢房為止?，F(xiàn)在要釋放a1,a2,...,aQ號囚犯，如何選擇釋放的順序，使得使用的金幣最少。

思路：

其中很重要的一點：釋放了某個囚犯以后，就把連續(xù)的牢房分成了沒有任何關(guān)系的兩段。
只要枚舉出所有的釋放囚犯的順序即可，復(fù)雜度為 O(Q3)。

利用動態(tài)規(guī)劃枚舉所有的情況的時候，我們有2種方法：
方法1.（自上而下）先選取首先釋放的囚犯。然后劃分沒兩段獨立的部分，然后對左右兩段再遞歸的調(diào)用。
方法2.（自下而上）利用動態(tài)規(guī)劃數(shù)組，例舉出所有最小的子問題，然后再根據(jù)最小的子問題可以組合成稍大一點的子問題。

用二叉樹的來表示可能更形象一點：
針對每個釋放順序，都可以用一個二叉樹來表示
例如：有 1-8個囚犯，釋放順序為：4，2，6的話
1、先釋放4

2、釋放2

3、釋放6

可以看出，當釋放4號的時候，就把原先的1-8號分為1-3號和5-8號兩段獨立的，所以上面的第二步和第三步其實可以交換的，
當然這個例子比較簡單，不過其實再復(fù)雜的問題也就是上面的這些情況的不斷疊加而已，比如上面這個二叉樹也可能是更大的二叉樹的一個部分。

然后我們再回過來，用二叉樹的表示方法來再來說一下上面的2個方法，可能方法1比較容易理解，人的一般思維方式都是這樣的，然后重點說說方法2
方法2的思想是：
例如要釋放 a1,a2,...,aQ囚犯，我們記為A[1]-A[Q],先分成最小的區(qū)間開始找，為了方便，我們把兩端也加入，這樣變?yōu)锳[0]-A[Q+1]
什么叫最小的區(qū)間？就是在區(qū)間里面只有一個要釋放的囚犯，這樣的區(qū)間（長度為2）是 A[0]?A[2],A[1]?A[3]..A[Q?1]?A[Q+1],求出其對應(yīng)的金幣，我們記為Cost[0][2],Cost[1][3]...Cost[Q?1][Q+1]
然后我們再找區(qū)間里面只有兩個要釋放的囚犯，這樣區(qū)間（長度為3）可以用上面長度為2的區(qū)間來求得 例如 A[0]-A[3]
如果先釋放1號，對應(yīng)的是Cost[1][3]加上a0與a1之間的囚犯數(shù)
如果先釋放2號，對應(yīng)的是Cost[0][2]加上a2與a3之間的囚犯數(shù)
然后Cost[0][3]就是上面值更小的一個情況
這樣不斷迭代，最后就可以求出Cost[0][Q+1]，就是最后的答案

枚舉的時候，由于可能會出現(xiàn)多次相同的情況，但前面又已經(jīng)計算過了，所以可以利用一個數(shù)組，來保存已經(jīng)計算過的情況（剪枝）。

代碼：

#include<stdio.h>
#define INT_MAX 0x3f3f3f3f
using namespace std;
int p,Q ;
//區(qū)間動態(tài)規(guī)劃
//bribe the prisoner
//定義一個二維數(shù)組。依次用來填充最小的花費。
int dp[109][109];//表示從第i個填充到j(luò)個時的最小花費。
//同時定義一個存放罪犯的數(shù)組。
int a[109];
void solve()
{
    a[0]=0;
    a[Q+1]=p+1;//為了解決邊界問題。
    for(int i=0; i<=Q; i++)
        dp[i][i+1]=0;//初始化，因為所有的從i到i+1的花費除去邊界都是0；
    //循環(huán)求解。定義w表示區(qū)間的范圍，w=2表示跨度為2的情況，也就是該區(qū)間里面只有一個要釋放的犯人
    for(int w=2; w<=Q+1; w++)
    {
        //每次選的范圍都是w，從i到j(luò) 的范圍內(nèi)的最小值等于從i到K加從第k到j(luò)的最小值。
        for(int i=0; i+w<=Q+1; i++)
        {
            //此處用到的k恰是其中的中值。
            int j=i+w,tmp=INT_MAX;//tmp用來保存當前區(qū)間的當前最好情況的花費金幣數(shù)
            for(int k=i+1; k<j; k++)
                tmp=min(tmp,dp[i][k]+dp[k][j]);
            dp[i][j]=tmp+a[j]-a[i]-2;//此處就是當前區(qū)間最小值。
        }
    }
    printf("%d
",dp[0][Q+1]);
}
int main()
{
    scanf("%d%d",&p,&Q);
    for(int i=1; i<=Q; i++)
        scanf("%d",&a[i]);
    solve();
    return 0;
}

總結(jié)

以上是生活随笔為你收集整理的贿赂囚犯 Bribe the prisoners （ 动态规划+剪枝）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。