[数据结构与算法]阿里数学竞赛之动态规划

"code and math are beautiful"

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?2021-9-3

一般涉及最值和多种情况之间关系的优先考虑动态规划

典型的"双蛋黄"动态规划:

解题思路:

1.首先设?为k个数量的杯子对应楼层T的最小检验次数,表示从t层摔下去后状态为state时还需检验的最小次数

2.首先临界层的定义是:杯子出现裂痕的层数

3.首先题目中提出假如t层为情况一，那么t+3才出现情况三

一:无破碎，无裂痕:

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? F(k,无破碎无裂痕)=M(k,T-t),t代表当前检验的楼层 t<=T

因为假如从t层摔下去仍无裂痕，表示在需在t~T层检验

二:无破碎，有裂痕:

? ? ? ? ? ? ? ? ? ? ? ? ? ???F(?k,无破碎有裂痕) ={0,t=1时? | |?1,t>1?} t代表当前检验的楼层 t<=T

因为当假如从第一层往下摔后，出现裂痕，表示临界层为0层，如果大于1，只需要再测试一次就行

三:有破碎，有裂痕:

? ? ? ? ? ? ? ? ? ? ? ? ? ? F(k,有破碎有裂痕)={0 ,t<=3||M(k-1,T-t),t>3} t代表当前检验的楼层 t<=T

假如从第三层摔下去后破了，表示临界层为0层,否则若t>3，则返回原始问题的最优子结构

四:建立动态方程

那么F(t)在t层的最小检验次数则为

? ? ? ? ? ? ? ? ? F(t)=max{F(k,无裂痕无破碎），F(k,无破碎有裂痕),F(k,有破碎有裂痕)}+1

取max是因为需取三者最大才能满足检验要求，+1是无论如何都得检验一次

而最小值则在1~T中循环遍历产生

即 F(t)=min(max{F(k,无裂痕无破碎），F(k,无破碎有裂痕),F(k,有破碎有裂痕)}+1),1<=t<=T

此时根据t的范围分为两种:

当t<=3时 F(t)=min(max{M(k,T-t),1,0}+1}

当t>3时? F(t)=min(max{M(k,T-t),1,M(k-1,T-t)}+1)

代码如下:

其中初始化解释:

1.当dp[i][1]即代表只有一个物品测试时，拿T层来说，有可能到了T层还是无破碎无裂痕，因此总共要测试T次

2.dp[1][i]即代表在楼层1往下摔，只需测试一次就能得出结果

3.每次遍历操作前一定要把dp[i][j]设为无穷大，才能保证结果正确

#define _CRT_SECURE_NO_WARNINGS
//#include<bits/stdc++.h>
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
#define bbn 100001
using namespace std;
const int T = 130;
const int N = 5;
const int INF = 1e20;
int dp[T][N];
int main()
{
    for (int i = 1; i <= T; i++) { dp[i][1] = i; }
    for (int i = 1; i <= N; i++) { dp[1][i] = 1; }
    for (int i = 2; i <= T; i++)//楼层1初始化过了 直接从2开始
    {
        for (int j = 2; j <= N; j++)//后面有减1的操作 所以j要设为2
        {
            dp[i][j] = INF;
            for (int k = 1; k < i; k++)//在1~i中的情况 
            {
                if (k < 4)
                {
                    dp[i][j] = min(dp[i][j], max(1, dp[i - k][j]) + 1);//这边0可以省略
                }
                else
                {
                    dp[i][j] = min(dp[i][j], max(dp[i - k][j], dp[k - 3][j - 1]) + 1);
                }
            }
        }
    }
    cout << dp[120][3] << endl;
    return 0;
    
}

最后得出程序结果为8

即表示只需从8个不同的楼层中往下摔即可保证准确测出N