原创

当时第一次看见状态转移方程这种解法时，简直被这种解法给感动住了，世上竟有如此简洁，强大之算法。其惊讶程度不亚于19世纪电磁物理学家听闻麦克斯韦方程组，20世纪理论物理学家接触弦理论和膜理论。在已有的记忆中上次有这么感觉，是在接触变分原理的The Euler-Lagrange方程的时候。

原题找不见了，大概就是这么个意思了：两个软硬程度一样但未知的鸡蛋，它们有可能都在一楼就摔碎，也可能从一百层楼摔下来没事。有座100层的建筑，要你用这两个鸡蛋确定哪一层是鸡蛋可以安全落下的最高位置。可以摔碎两个鸡蛋。

sh*t，刚才搜到了极像的原题：

当当当~

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

---

有点难哟~

你也许深知事物的矛盾性，两面性，于是你会用快速的，直接的，暴力的上古神器，蕴含了大智慧的哲学结晶-二分法。

如果你有很多鸡蛋（正无穷个），以及碰到一位完全没有脾气的搭档清扫摔碎的鸡蛋，这不失为一种完美方法。

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

动态规划（dynamic programming），或者叫dp终于要粉墨登场了。

我觉得如果有状态转移方程，绝壁是其题解核心。

状态转移方程，是动态规划中本阶段的状态往往是上一阶段状态和上一阶段决策的结果。如果给定了第K阶段的状态Sk以及决策uk(Sk)，则第K+1阶段的状态Sk+1也就完全确定。

• 1.最优化原理（最优子结构性质） 最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。

• 2.无后效性将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。 [2]

• 3.子问题的重叠性 动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。

终于扯完没用的了，开始分析这个题准备写代码。

如果你从第x层往下摔鸡蛋，有没摔烂和摔烂两种情况。如果摔烂了，就从上一次没摔碎的地方往上摔？？

函数的书写看着像从某状态往前推，其实推导过程在for循环里，从初始状态往后推的。

#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 个鸡蛋的最小判断次数

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;//初始化为比较大的值,为后面的数据覆盖做打算。

            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

可能你学习过Floyd算法，算了，这儿写一下Floyd的算法代码以供参考。

for(int k=0;k<n;k++){//k表示中间经过的点

    for(int i=0;i<n;i++){//i，j表示对于图中所有节点对

        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理解起来并不容易。

因为k应该是在最内层循环的呀，即使是用状态转移方程来理解，k也应该在最内层。

其实不然，状态转移方程是个递推的式子。应该保证所转移之前的状态必须是准确的。

这样你会发现咱们Floyd写的只是Floyd状态转移方程的变形。

image

这才是Floyd动态规划的状态转移方程，在知道f[k][i][j](其表示的是在1~k之内的最短路径，k后面的点并没有录入，判断）之前必须先知道f[k-1][i][j]与f[k-1][i][k]+f[k-1][k][j];

你可能会疑问这和上个题转移到k过程一样，那k应该还是在最内层啊，以及为什么k在数组位置要放在最前面啊。

因为在这儿，i和j是已知的，i和j之间的中间状态k是变化的，需要动态规划的。

k放哪儿都一样，如同i和j放哪儿也都一样，但是因为内部有k-1的递推。即为了知道k必须知道k-1，故滚动数字k是占统治地位的。

如此可把k剥离出，因为f[k]与f[k-1]只是个递推和循环的关系，只留在外循环里即可。

如此简化成

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个点（n≤100），每个点的坐标均在-10000~10000之间。其中的一些点之间有连线。
若有连线，则表示可从一个点到达另一个点，即两点间有通路，通路的距离为两点间的直线距离。现在的任务是找出从一点到另一点之间的最短路径。
【输入】
共n+m+3行，其中:
第一行为整数n。
第2行到第n+1行（共n行） ，每行两个整数x和y，描述了一个点的坐标。
第n+2行为一个整数m，表示图中连线的个数。
此后的m 行，每行描述一条连线，由两个整数i和j组成，表示第i个点和第j个点之间有连线。
最后一行：两个整数s和t，分别表示源点和目标点。
【输出】
一行，一个实数（保留两位小数），表示从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初始化一个巨大的值，并且发现3维数组无法直接赋值。

BerryKanry；

DP思想很关键。

如果k不在最外层，就不能保证每次都是最小值，。就是这样了。