【备战蓝桥杯】吃奶酪问题 / 超硬核,文附template拓展知识!

发布时间:2024年01月18日

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


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

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

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

  • 再来了解一下状压dp

简介(Introduction)

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

描述(Description)

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

- 吃奶酪

题目描述

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

输入格式

第一行有一个整数,表示奶酪的数量 n n n

2 2 2 到第 ( n + 1 ) (n + 1) (n+1) 行,每行两个实数,第 ( i + 1 ) (i + 1) (i+1) 行的实数分别表示第 i i i 块奶酪的横纵坐标 x i , y i x_i, y_i xi?,yi?

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

7.41

提示

数据规模与约定

对于全部的测试点,保证 1 ≤ n ≤ 15 1\leq n\leq 15 1n15 ∣ x i ∣ , ∣ y i ∣ ≤ 200 |x_i|, |y_i| \leq 200 xi?,yi?200,小数点后最多有 3 3 3 位数字。

提示

对于两个点 ( x 1 , y 1 ) (x_1,y_1) (x1?,y1?) ( x 2 , y 2 ) (x_2, y_2) (x2?,y2?),两点之间的距离公式为 ( x 1 ? x 2 ) 2 + ( y 1 ? y 2 ) 2 \sqrt{(x_1-x_2)^2+(y_1-y_2)^2} (x1??x2?)2+(y1??y2?)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后成功编译并运行出正确结果真的会感到很幸福!

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

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

文章来源:https://blog.csdn.net/m0_73246124/article/details/135662484
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。