个人电脑 网站 备案,网站上网络营销,58上海同城网,淘宝指数查询蓝桥杯备赛 | 洛谷做题打卡day9 文章目录 蓝桥杯备赛 | 洛谷做题打卡day9再来了解一下状压dp**简介(Introduction)****描述(Description)** - 吃奶酪题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示数据规模与约定提示 * template拓展知识我的一些话 【引入】今天… 蓝桥杯备赛 | 洛谷做题打卡day9 文章目录 蓝桥杯备赛 | 洛谷做题打卡day9再来了解一下状压dp**简介(Introduction)****描述(Description)** - 吃奶酪题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示数据规模与约定提示 * template拓展知识我的一些话 【引入】今天的题目要用到
动态规划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) (n1) 行每行两个实数第 ( i 1 ) (i 1) (i1) 行的实数分别表示第 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 1≤n≤15 ∣ 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以下是题解代码 ~ #includecstdio
#includecmath
#includecstring
typedef double db;//typedef 自定义数据类型可用于简化书写例如此行将double数据类型简写成db
db x[20],y[20],f[20][35000];
templateclass T T min(T a,T b) {return ab?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 i1;in;i) scanf(%lf%lf,x[i],y[i]);memset(f,127,sizeof(f));//初始化集合为最大值for(int s1;s(1n)-1;s)//位运算符1n表示对数字1进行左移n位操作。这意味着将二进制数1向左移动n个位置然后用0填充右侧空出的位,总之这个操作相当于将1乘以2的n次方for(int i1;in;i){if((s(1(i-1)))0) continue;if(s(1(i-1))) {f[i][s]0;continue;}for(int j1;jn;j){if((s(1(j-1)))0||ij) continue;f[i][s]min(f[i][s],f[j][s-(1(i-1))]dis(i,j));}}db ans-1;for(int i1;in;i){db sf[i][(1n)-1]dis(i,0);if(ans-1||anss) anss;}printf(%.2lf\n,ans);return 0;
}* template拓展知识
关于题解中template T min(T a,T b) {return ab?a:b;}的详细解释 这是一个C的函数模板用于比较两个值并返回较小的那个值。让我们逐步解释这个函数模板的各个部分 1.templateclass T这是函数模板的声明表明接下来的函数定义中将使用一个通用类型 T。通用类型允许在调用函数时传递不同类型的参数。 2.T min(T a, T b)这是函数模板的定义。它接受两个参数 a 和 b这两个参数的类型都是 T。函数返回类型仍然是 T因为我们要返回两者中较小的那个值。 3.{return ab?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后成功编译并运行出正确结果真的会感到很幸福 关于之前蓝桥杯备赛的路线和基本方法、要掌握的知识之前的博文我都有写欢迎大家关注我翻阅自取哦~ 不管什么都要坚持吧三天打鱼两天晒网无法形成肌肉记忆和做题思维该思考的时候一定不要懈怠今天就说这么多啦欢迎关注留言一起成长
