蓝桥杯备赛 | 洛谷做题打卡day9

【引入】今天的题目要用到 动态规划DP的知识，因此先给大家普及一下背景：

​ 动态规划法是20世纪50年代由贝尔曼（R. Bellman）等人提出，用来解决多阶段决策过程问题的一种最优化方法。所谓多阶段决策过程，就是把研究问题分成若干个相互联系的阶段，由每个阶段都作出决策，从而使整个过程达到最优化。许多实际问题利用动态规划法处理，常比线性规划法更为有效，特别是对于那些离散型问题。实际上，动态规划法就是分多阶段进行决策，其基本思路是：按时空特点将复杂问题划分为相互联系的若干个阶段，在选定系统行进方向之后，逆着这个行进方向，从终点向始点计算，逐次对每个阶段寻找某种决策，使整个过程达到最优，故又称为逆序决策过程。

​ 其基本思想是将原问题分解为相似的子问题，在求解的过程中通过子问题的解求出原问题的解。动态规划的思想是多种算法的基础，被广泛应用于计算机科学和工程领域。动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。

• 再来了解一下状压dp

简介(Introduction)

状压DP即状态压缩DP，指通过特殊的方法来压缩存储所要表达的状态。

描述(Description)

状态压缩DP属于DP问题中比较困难的一类问题，对于状态的压缩模拟和对题目状态的转移需要较强的理解。

- 吃奶酪

题目描述

房间里放着 $n$ 块奶酪。一只小老鼠要把它们都吃掉，问至少要跑多少距离？老鼠一开始在 $(0,0)$ 点处。

输入格式

第一行有一个整数，表示奶酪的数量 $n$。

第 $2$ 到第 $(n+1)$ 行，每行两个实数，第 $(i+1)$ 行的实数分别表示第 $i$ 块奶酪的横纵坐标 $x_i,y_i$。

输出格式

输出一行一个实数，表示要跑的最少距离，保留 $2$ 位小数。

样例 #1

样例输入 #1

4
1 1
1 -1
-1 1
-1 -1

样例输出 #1

7.41

提示

数据规模与约定

对于全部的测试点，保证 $1\le n\le 15$，$|x_i|,|y_i|\le 200$，小数点后最多有 $3$ 位数字。

提示

对于两个点 $(x_1,y_1)$，$(x_2,y_2)$，两点之间的距离公式为 $\sqrt{(x_1-x_2{)}^2+(y_1-y_2{)}^2}$。

---

学会利用新知，自己多试试并尝试积攒一些固定解答方案，debug，以下是题解代码 ~

#include<cstdio>
#include<cmath>
#include<cstring>
typedef double db;//typedef 自定义数据类型，可用于简化书写，例如此行将double数据类型简写成db
db x[20],y[20],f[20][35000];
template<class T> T min(T a,T b) {return a<b?a:b;}//Template泛型编程,关于它的详细解释我会在文末给出，感兴趣可自行阅读
db dis(int a,int b) {return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));}//定义距离函数
int main()
{
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lf%lf",&x[i],&y[i]);
    memset(f,127,sizeof(f));//初始化集合为最大值
    for(int s=1;s<=(1<<n)-1;s++)//位运算符<<，1<<n表示对数字1进行左移n位操作。这意味着将二进制数1向左移动n个位置，然后用0填充右侧空出的位,总之这个操作相当于将1乘以2的n次方
    for(int i=1;i<=n;i++)
    {
        if((s&(1<<(i-1)))==0) continue;
        if(s==(1<<(i-1))) {f[i][s]=0;continue;}
        for(int j=1;j<=n;j++)
        {
            if((s&(1<<(j-1)))==0||i==j) continue;
            f[i][s]=min(f[i][s],f[j][s-(1<<(i-1))]+dis(i,j));
        }
    }
    db ans=-1;
    for(int i=1;i<=n;i++)
    {
        db s=f[i][(1<<n)-1]+dis(i,0);
        if(ans==-1||ans>s) ans=s;
    }
    printf("%.2lf\n",ans);
    return 0;
}

* template拓展知识

关于题解中template T min(T a,T b) {return a<b?a:b;}的详细解释：

这是一个C++的函数模板，用于比较两个值并返回较小的那个值。让我们逐步解释这个函数模板的各个部分：

1.template<class T>：这是函数模板的声明，表明接下来的函数定义中将使用一个通用类型 T。通用类型允许在调用函数时传递不同类型的参数。
2.T min(T a, T b)：这是函数模板的定义。它接受两个参数 a 和 b，这两个参数的类型都是 T。函数返回类型仍然是 T，因为我们要返回两者中较小的那个值。
3.{return a<b?a:b;}：这是函数的实际实现。它使用条件运算符 a < b ? a : b 来比较 a 和 b 的大小。如果 a 小于 b，则返回 a，否则返回 b。

让我们看一个简单的例子，如果你调用 min 函数模板并传递两个整数：
int result = min(3, 7);

在这种情况下，T 将被推导为 int，因为传递的参数是整数。函数将返回 3，因为 3 小于 7。这个函数模板可以灵活地适用于不同类型的参数，包括整数、浮点数等。

*想了解更多关于template知识的可以留言喔，之后可以进一步深入向大家科普泛型编程知识 (＾－＾)！

我的一些话

• 今天算是动态规划dynamic planning初步啦，状压dp确实有一定难度，需要通盘的考虑和理解，以及扎实的基础才能独立写出AC代码。但无论难易，大家都要持续做题，保持题感喔！一起坚持(o´ω`o)

• 总结来说思路很重要，多想想，多在草稿纸上画画，用测试数据多调试，debug后成功编译并运行出正确结果真的会感到很幸福！

• 关于之前蓝桥杯备赛的路线和基本方法、要掌握的知识，之前的博文我都有写，欢迎大家关注我，翻阅自取哦~

• 不管什么都要坚持吧，三天打鱼两天晒网无法形成肌肉记忆和做题思维，该思考的时候一定不要懈怠，今天就说这么多啦，欢迎关注留言，一起成长：）