原創(chuàng)

當(dāng)時第一次看見狀態(tài)轉(zhuǎn)移方程這種解法時，簡直被這種解法給感動住了，世上竟有如此簡潔，強(qiáng)大之算法。其驚訝程度不亞于19世紀(jì)電磁物理學(xué)家聽聞麥克斯韋方程組，20世紀(jì)理論物理學(xué)家接觸弦理論和膜理論。在已有的記憶中上次有這么感覺，是在接觸變分原理的The Euler-Lagrange方程的時候。

原題找不見了，大概就是這么個意思了：兩個軟硬程度一樣但未知的雞蛋，它們有可能都在一樓就摔碎，也可能從一百層樓摔下來沒事。有座100層的建筑，要你用這兩個雞蛋確定哪一層是雞蛋可以安全落下的最高位置?？梢运に閮蓚€雞蛋。

sh*t，剛才搜到了極像的原題：

當(dāng)當(dāng)當(dāng)~

Balls
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 892Accepted: 588
Description
The classic Two Glass Balls brain-teaser is often posed as:
“Given two identical glass spheres, you would like to determine the lowest floor in a 100-story building from which they will break when dropped. Assume the spheres are undamaged when dropped below this point. What is the strategy that will minimize the worst-case scenario for number of drops?”
Suppose that we had only one ball. We’d have to drop from each floor from 1 to 100 in sequence, requiring 100 drops in the worst case.
Now consider the case where we have two balls. Suppose we drop the first ball from floor n. If it breaks we’re in the case where we have one ball remaining and we need to drop from floors 1 to n-1 in sequence, yielding n drops in the worst case (the first ball is dropped once, the second at most n-1 times). However, if it does not break when dropped from floor n, we have reduced the problem to dropping from floors n+1 to 100. In either case we must keep in mind that we’ve already used one drop. So the minimum number of drops, in the worst case, is the minimum over all n.
You will write a program to determine the minimum number of drops required, in the worst case, given B balls and an M-story building.
Input
The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow. Each data set consists of a single line containing three(3) decimal integer values: the problem number, followed by a space, followed by the number of balls B, (1 ≤ B ≤ 50), followed by a space and the number of floors in the building M, (1 ≤ M ≤ 1000).
Output
For each data set, generate one line of output with the following values: The data set number as a decimal integer, a space, and the minimum number of drops needed for the corresponding values of B and M.
Sample Input
4
1 2 10
2 2 100
3 2 300
4 25 900
Sample Output
1 4
2 14
3 24
4 10

有點(diǎn)難喲~

你也許深知事物的矛盾性，兩面性，于是你會用快速的，直接的，暴力的上古神器，蘊(yùn)含了大智慧的哲學(xué)結(jié)晶-二分法。

如果你有很多雞蛋（正無窮個），以及碰到一位完全沒有脾氣的搭檔清掃摔碎的雞蛋，這不失為一種完美方法。

But，you just have two eggs，yes，they are。

動態(tài)規(guī)劃（dynamic programming），或者叫dp終于要粉墨登場了。

我覺得如果有狀態(tài)轉(zhuǎn)移方程，絕壁是其題解核心。

狀態(tài)轉(zhuǎn)移方程，是動態(tài)規(guī)劃中本階段的狀態(tài)往往是上一階段狀態(tài)和上一階段決策的結(jié)果。如果給定了第K階段的狀態(tài)Sk以及決策uk(Sk)，則第K+1階段的狀態(tài)Sk+1也就完全確定。

• 1.最優(yōu)化原理（最優(yōu)子結(jié)構(gòu)性質(zhì)） 最優(yōu)化原理可這樣闡述：一個最優(yōu)化策略具有這樣的性質(zhì)，不論過去狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。簡而言之，一個最優(yōu)化策略的子策略總是最優(yōu)的。一個問題滿足最優(yōu)化原理又稱其具有最優(yōu)子結(jié)構(gòu)性質(zhì)。

• 2.無后效性將各階段按照一定的次序排列好之后，對于某個給定的階段狀態(tài)，它以前各階段的狀態(tài)無法直接影響它未來的決策，而只能通過當(dāng)前的這個狀態(tài)。換句話說，每個狀態(tài)都是過去歷史的一個完整總結(jié)。這就是無后向性，又稱為無后效性。 [2]

• 3.子問題的重疊性 動態(tài)規(guī)劃將原來具有指數(shù)級時間復(fù)雜度的搜索算法改進(jìn)成了具有多項(xiàng)式時間復(fù)雜度的算法。其中的關(guān)鍵在于解決冗余，這是動態(tài)規(guī)劃算法的根本目的。動態(tài)規(guī)劃實(shí)質(zhì)上是一種以空間換時間的技術(shù)，它在實(shí)現(xiàn)的過程中，不得不存儲產(chǎn)生過程中的各種狀態(tài)，所以它的空間復(fù)雜度要大于其它的算法。

終于扯完沒用的了，開始分析這個題準(zhǔn)備寫代碼。

如果你從第x層往下摔雞蛋，有沒摔爛和摔爛兩種情況。如果摔爛了，就從上一次沒摔碎的地方往上摔？？

函數(shù)的書寫看著像從某狀態(tài)往前推，其實(shí)推導(dǎo)過程在for循環(huán)里，從初始狀態(tài)往后推的。

#include <iostream>

#include<cstring>

using namespace std;

const int INF = 1e9+5;

const int  MAXN=1010;

int dp[MAXN][60];//dp[i][j]:表示在 i 層樓 還有 j 個雞蛋的最小判斷次數(shù)

void Solve(int M, int N)

{

    memset(dp, 0, sizeof(dp));//初始化

    for(int i=1; i<=N; i++)//就一個雞蛋，肯定是從第一層往上嘗試的

        dp[i][1] = i;

    for(int i=1; i<=M; i++)//就一層，肯定是 1

        dp[1][i] = 1;

    for(int i=1; i<=N; i++)

    {

        for(int j=2; j<=M; j++)

        {

            dp[i][j] = INF;//初始化為比較大的值,為后面的數(shù)據(jù)覆蓋做打算。

            for(int k=1; k<=i; k++)

                dp[i][j] = min(dp[i][j],max(dp[k-1][j-1],dp[i-k][j])+1);

        }

    }

}

int main()

{

    int op, N, M, T;

    cin>>T;

    while(T--)

    {

        cin>>op>>M>>N;//N層 M個

        Solve(M, N);

        cout<<op<<" "<<dp[N][M]<<endl;

    }

    return 0;

}

大晚上在宿舍拍的圖，講究食用吧。

image

可能你學(xué)習(xí)過Floyd算法，算了，這兒寫一下Floyd的算法代碼以供參考。

for(int k=0;k<n;k++){//k表示中間經(jīng)過的點(diǎn)

    for(int i=0;i<n;i++){//i，j表示對于圖中所有節(jié)點(diǎn)對

        for(int j=0;j<n;j++){

            if(dis[i][j]>dis[i][k]+dis[k][j]) {

                dis[i][j]=dis[i][k]+dis[k][j];

            }

        }

    }

}

雖然是求最短路徑的最簡單的代碼（作用因此受限），相比于迪杰斯特拉算法，代碼夠短，but理解起來并不容易。

因?yàn)閗應(yīng)該是在最內(nèi)層循環(huán)的呀，即使是用狀態(tài)轉(zhuǎn)移方程來理解，k也應(yīng)該在最內(nèi)層。

其實(shí)不然，狀態(tài)轉(zhuǎn)移方程是個遞推的式子。應(yīng)該保證所轉(zhuǎn)移之前的狀態(tài)必須是準(zhǔn)確的。

這樣你會發(fā)現(xiàn)咱們Floyd寫的只是Floyd狀態(tài)轉(zhuǎn)移方程的變形。

image

這才是Floyd動態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移方程，在知道f[k][i][j](其表示的是在1~k之內(nèi)的最短路徑，k后面的點(diǎn)并沒有錄入，判斷）之前必須先知道f[k-1][i][j]與f[k-1][i][k]+f[k-1][k][j];

你可能會疑問這和上個題轉(zhuǎn)移到k過程一樣，那k應(yīng)該還是在最內(nèi)層啊，以及為什么k在數(shù)組位置要放在最前面啊。

因?yàn)樵谶@兒，i和j是已知的，i和j之間的中間狀態(tài)k是變化的，需要動態(tài)規(guī)劃的。

k放哪兒都一樣，如同i和j放哪兒也都一樣，但是因?yàn)閮?nèi)部有k-1的遞推。即為了知道k必須知道k-1，故滾動數(shù)字k是占統(tǒng)治地位的。

如此可把k剝離出，因?yàn)閒[k]與f[k-1]只是個遞推和循環(huán)的關(guān)系，只留在外循環(huán)里即可。

如此簡化成

f[i][j]=min(f[i][j],f[i][k]+f[k][j]);把k放在最外層。

為了具體說明問題，那個例題做例子吧。

題目作者：pxlsdz
題目來源：CSDN
題目原文：https://blog.csdn.net/sdz20172133/article/details/80028856
【題目描述】
平面上有n個點(diǎn)（n≤100），每個點(diǎn)的坐標(biāo)均在-10000~10000之間。其中的一些點(diǎn)之間有連線。
若有連線，則表示可從一個點(diǎn)到達(dá)另一個點(diǎn)，即兩點(diǎn)間有通路，通路的距離為兩點(diǎn)間的直線距離?，F(xiàn)在的任務(wù)是找出從一點(diǎn)到另一點(diǎn)之間的最短路徑。
【輸入】
共n+m+3行，其中:
第一行為整數(shù)n。
第2行到第n+1行（共n行） ，每行兩個整數(shù)x和y，描述了一個點(diǎn)的坐標(biāo)。
第n+2行為一個整數(shù)m，表示圖中連線的個數(shù)。
此后的m 行，每行描述一條連線，由兩個整數(shù)i和j組成，表示第i個點(diǎn)和第j個點(diǎn)之間有連線。
最后一行：兩個整數(shù)s和t，分別表示源點(diǎn)和目標(biāo)點(diǎn)。
【輸出】
一行，一個實(shí)數(shù)（保留兩位小數(shù)），表示從s到t的最短路徑長度。
【輸入樣例】
5
0 0
2 0
2 2
0 2
3 1
5
1 2
1 3
1 4
2 5
3 5
1 5
【輸出樣例】
3.41

先上一個最最簡單的Floyd算法，亦是該題之正解。

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int INF 0x3f3f3f;

int a[105][2];

//double d[105][105][105];

double d[105][105];

int main()

{

    int x,y;

      int n,m;

  cin>>n;

  int i,j,k;

    memset(d,INF,sizeof(d));

  for(i=1;i<=n;i++)

  {

    cin>>a[i][1]>>a[i][2];

  }

  cin>>m;

  for(i=1;i<=m;i++)//鄰接矩陣

  {

      cin>>x>>y;

    d[x][y]=d[y][x]=sqrt(a[x][1]-a[y][1]*a[x][1]-a[y][1]*1.0+a[x][2]-a[y][2]*a[x][2]-a[y][2]*1.0);

  }

    for(int k = 1; k <= n; k++)

        for(int i = 1; i <= n; i++)

            for(int j = 1; j <= n; j++)

            {

                if(i!=j&&i!=k&&j!=k)

                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

            }

    int b,e;

    cin>>b>>e;

    printf("%.2lf\n",d[b][e]);

  return 0;

}

#include<bits/stdc++.h>

using namespace std;

#define N 2001

int a[105][2];

double d[105][105][105];

//double d[105][105];

int main()

{

    int x,y;

      int n,m;

  cin>>n;

  int i,j,k;

    memset(d,0x7f,sizeof(d));//將d初始化成一個很大的值

  for(i=1;i<=n;i++)

  {

    cin>>a[i][1]>>a[i][2];

  }

  cin>>m;

  for(i=1;i<=m;i++)//鄰接矩陣

  {

      cin>>x>>y;

    d[0][x][y]=d[0][y][x]=sqrt(pow(double(a[x][1]-a[y][1]),2)+pow(double(a[x][2]-a[y][2]),2));

    //d[x][y]=d[y][x]=sqrt(pow(double(a[x][1]-a[y][1]),2)+pow(double(a[x][2]-a[y][2]),2));

  }

  //floyed算法

        for(int i = 1; i <= n; i++)

            for(int j = 1;j <= n ;j++ )

          for(int k = 1; k <= n; k++)

            {

                //if(i!=j&&i!=k&&j!=k)

                d[k][i][j] = min(d[k-1][i][j], d[k-1][i][k] + d[k-1][k][j]);

            }

    int b,e;

    cin>>b>>e;

    printf("%.2lf\n",d[n][1][2]+d[n][2][5]);

  return 0;

}

memset(d,0x7f,sizeof(d));給d初始化一個巨大的值，并且發(fā)現(xiàn)3維數(shù)組無法直接賦值。

BerryKanry；

DP思想很關(guān)鍵。

如果k不在最外層，就不能保證每次都是最小值，。就是這樣了。