返回頂部

『嗨威說』算法設計與分析 - 動態規劃思想小結(HDU 4283 You Are the One)

本文索引目錄:

一、動態規劃的基本思想

二、單調遞增最長子序列、租用游艇問題(PTA)遞歸方程

三、一道區間動態規劃題點撥升華動態規劃思想

四、結對編程情況

 

 

一、動態規劃的基本思想:

  1.1  基本概念:

  動態規劃算法簡單說,利用拆解問題思想,定義問題狀態和狀態之間的關系,使得問題能夠以遞推或者是分治的方式去解決。
  動態規劃算法的基本思想與分治法很相似,將待求解的問題分解為若干個子問題,前一子問題的解,為后一子問題的求解所依賴。在求解任一子問題時,列出各種可能的局部解,通過決策保留那些有可能達到最優的局部解,丟棄其他局部解。依次解決各子問題,最后一個子問題就是初始問題的解。

 

  1.2  使用條件:

  (1)具有最優子結構

具有最優子結構也可能是適合用貪心的方法求解。

注意要確保我們考察了最優解中用到的所有子問題。

1、證明問題最優解的第一個組成部分是做出一個選擇;

2、對于一個給定問題,在其可能的第一步選擇中,你界定已經知道哪種選擇才會得到最優解。你現在并不關心這種選擇具體是如何得到的,只是假定已經知道了這種選擇;

3、給定可獲得的最優解的選擇后,確定這次選擇會產生哪些子問題,以及如何最好地刻畫子問題空間;

4、證明作為構成原問題最優解的組成部分,每個子問題的解就是它本身的最優解。方法是反證法,考慮加入某個子問題的解不是其自身的最優解,那么就可以從原問題的解中用該子問題的最優解替換掉當前的非最優解,從而得到原問題的一個更優的解,從而與原問題最優解的假設矛盾。

要保持子問題空間盡量簡單,只在必要時擴展。 最優子結構的不同體現在兩個方面: 原問題的最優解中涉及多少個子問題; 確定最優解使用哪些子問題時,需要考察多少種選擇。 子問題圖中每個定點對應一個子問題,而需要考察的選擇對應關聯至子問題頂點的邊。

   (2)子問題重疊

子問題空間要足夠小,即問題的遞歸算法會反復地求解相同的子問題,而不是一直生成新的子問題。

 

  1.3  使用思想:

(1)首先是拆分問題,將問題劃分成一步一步這樣就可以通過遞推或者遞歸來實現。
(2)其次定義問題狀態和狀態之間的關系,前面拆分的步驟之間的關系,用一種量化的形式表現出來,也即狀態轉移方程式。

  1.4  動態規劃的問題種類:

(1)背包動態規劃問題

(2)區間動態規劃問題

(3)有向無環圖的動態規劃問題

(4)樹形動態規劃問題

(5)狀態壓縮動態規劃問題

(6)數位動態規劃問題

(7)插頭動態規劃問題

(8)計數動態規劃問題

(9)實時動態規劃問題

(10)動態規劃優化問題等

 

 

二、單調遞增最長子序列、租用游艇問題(PTA)遞歸方程:

  單調遞增最長子序列:dp[ i ] 表示當前以a[i]結束時之前的遞增子序列的最大長度。

         /* 動規轉移方程: dp[ i ] = max(1,dp[ j ] + 1) 【滿足aj<ai且j<i】;*/

  租用游艇問題:dp[ i ] 表示到i站時的最小租金 

         /* 動規轉移方程:dp[ i ] = min(dp[ i ],dp[ j ] + temp[ j ][ i ]);【滿足j<i】*/

 

 

三、一道區間動態規劃題點撥升華動態規劃思想:

2.1  題目來源:

Vjudge:https://vjudge.net/contest/112701#problem/G

 

2.2  題目題干:

 You Are the One  

 

 

 2.3  題目大意:

  題目意思是:給定一個有序隊伍,在進入舞臺前,需要先進入一個狹小的黑屋子,最先進去的人最后出來,進入舞臺的順序會影響到每個人的憤怒值,每個人上臺的時候的憤怒值為第k個人上場乘以自己的屌絲值,試問怎么安排人員進出狹小黑屋子能實現最小化憤怒值?

  這個問題簡化來說,就是給定一個有序隊列,進入一個棧中(也即題目的狹小黑屋子),然后通過不斷地進棧出棧實現人員順序調整,最后使得上臺之后的所有人憤怒值總和最小。

 

2.4  題目思路:

  首先介紹一下區間DP:

  定義:區間dp就是在區間上進行動態規劃,求解一段區間上的最優解。主要是通過合并小區間的 最優解進而得出整個大區間上最優解的dp算法。

  核心思路:既然讓我求解在一個區間上的最優解,那么我把這個區間分割成一個個小區間,求解每個小區間的最優解,再合并小區間得到大區間即可。所以在代碼實現上,我可以枚舉區間長度len為每次分割成的小區間長度(由短到長不斷合并),內層枚舉該長度下可以的起點,自然終點也就明了了。然后在這個起點終點之間枚舉分割點,求解這段小區間在某個分割點下的最優解。

  基本模板:

for(int len = 1;len<=n;len++){//枚舉長度
        for(int j = 1;j+len<=n+1;j++){//枚舉起點,ends<=n
            int ends = j+len - 1;
            for(int i = j;i<ends;i++){//枚舉分割點,更新小區間最優解
                dp[j][ends] = min(dp[j][ends],dp[j][i]+dp[i+1][ends]+something);
            }
        }
    }

 

  本題思路:

  題意給出n個人,每個人都有他們自己的屌絲值,第k個人出場的憤怒值為(k-1)*屌絲值,現在有一個棧,可以通過棧的入棧出棧操作來實現調整隊伍的方法,可以很明顯的了解到這能夠使用區間DP,也即把一個大的區間去轉化成兩個小區間,思想有點類似于分治法,對于一個人,如果他是第k個出場的,那么一定是i到i+k-1中以一種方式出場,然后這個人出場,然后i+k到j以一種方式出場,這樣就分成了三個區間,[i,i]、[i+1,i+k-1]、[i+k,j]這三個區間。

令 dp[i][j] 表示從 i 到 j 這些人以一種出場順序的最小值。
那么對于剛剛劃分出來的三個區間 我們可以得到 dp[i][j] = dp[i+1][i+k-1] + (k-1)*a[i] + (sum[j]-sum[i+k-1])*k + dp[i+k][j]
dp[i+1][i+k-1] :表示先出場這一批人的最小憤怒值
(k-1)*a[i] :表示 i 出場時的憤怒值
dp[i+k][j] :表示后面這一批人的最小憤怒值
(sum[j]-sum[i+k-1])*k :表示后面這一批人需要額外加上的憤怒值

 

2.5  題目AC代碼:

#include<bits/stdc++.h>
using namespace std;

int times;
int dp[1005][1005];
int main()
{
    ios::sync_with_stdio(false);
    cin>>times;
    for(int i = 1;i<=times;i++)
    {
        int temp;
        cin>>temp;
        int *mark = new int[temp+1];
        int *ans = new int[temp+1];
        ans[0] = 0;
        
        
        for(int i = 1;i<=temp;i++)
        {
            ans[i] = 0;
            cin>>mark[i];
            ans[i] = ans[i-1] + mark[i];
        }
        
        
        for(int i=1;i<1005;i++)
        {
            for(int j=i+1;j<1005;j++)
                dp[i][j]=999999999;
        }
        
        for(int d=2; d<=temp; d++) {
            for(int i=1, j=d; j<=temp; i++, j++) {
                for(int k=1; k<=j-i+1; k++) {
                    dp[i][j] = min(dp[i][j], dp[i+1][i+k-1]+dp[i+k][j]+(ans[j]-ans[i+k-1])*k+mark[i]*(k-1));
                }
            }
        }

        cout<<"Case #"<<i<<": "<<dp[1][temp]<<endl;
    }
 }

 

 

四、 結對編程情況:

 

 

  經過第一次實踐合作之后,第二次的實踐合作更加順利流暢,能夠讓雙方都能在相同思路上齊頭并進,當和三木小哥哥想到一起完成了算法設計、完成代碼書寫、成功AC一題之后,一種喜悅感涌上心頭,雖然第三題有一小點WA了,不過還是很合作默契的哈哈,感謝三木小哥哥一直包容我的錯誤哈哈哈哈。

  相信在下一次結對編程會愈發順利,加油。

 

 

如有不合理的地方,請及時指正,我愿聽取改正~

參考鏈接:https://oi-wiki.org/

posted @ 2019-10-26 14:19  嗨威er  閱讀(...)  評論(... 編輯 收藏
三d开奖结果走势图