方向标 | c++ | 动态规划

这篇具有很好参考价值的文章主要介绍了方向标 | c++ | 动态规划。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、题目描述

A carpenter has received an order for a wooden directional sign. Each board must be aligned vertically with the previous one, either to the basis of the previous arrowhead or to the opposite side, being fixed there with a specially designed screw. The two boards must overlap. The carpenter wrote down a sequence of integers to encode the sketch sent by the designer but the sequence does not determine a unique model and he has thrown away the original sketch. What looked like a trivial task turned out a big jigsaw to him.

a carpenter has received an order for a wooden directional,程序设计方法与实践2022,c++

The sequence (with 1 + N elements) encodes the (N) arrows from the bottom to the top of the sign. The first element is the position of the left side of the bottom arrow. The remaining N elements define the positions where the arrowheads start, from bottom to top: the i-th element is the position where the i-th arrowhead basis is. For instance, the two signs depicted (on the left and on the right) could be encoded by 2 6 5 1 4.

Since a board must be aligned vertically with the previous one (either to the basis of the previous arrowhead or to the opposite side), if the sequence was 2 6 5 1 4 3, the fifth arrow could be fixed (in any of the depicted signs) with a screw either at 1 (pointing to the right) or at 4 (pointing to the left), with the arrowhead basis at 3.

If the sequence was 2 3 1, the second arrow could only be fixed with a screw at 3, pointing to the left, because consecutive boards must overlap.

 a carpenter has received an order for a wooden directional,程序设计方法与实践2022,c++

All arrowheads are similar and the designer told the carpenter that their bases stand in different vertical lines, as well as the left side of the bottom arrow, altogether forming a permutation of 1..(N +1). That is why the carpenter overlooked the details and just wrote down the permutation (e.g., 2 6 5 1 4 3).

Given the sequence of numbers the carpenter wrote down, compute the number of directional arrows signs that can be crafted. Since the number can be very large, you must write it modulo 2147483647. The second integer in the sequence is always greater than the first one (the bottom arrow points to the right always).

Input

The first line has one integer N and the second line contains a permutation of the integers from 1 to N + 1. Integers in the same line are separated by a single space.

Output

The output has a single line with the number (modulo 2147483647) of distinct signs that can be described by the given permutation.

Note

1 ≤ N ≤ 2

测试输入 期待的输出 时间限制 内存限制 额外进程
测试用例 1 以文本方式显示
  1. 2↵
  2. 2 3 1↵
以文本方式显示
  1. 1↵
1秒 64M 0
测试用例 2 以文本方式显示
  1. 5↵
  2. 2 6 5 1 4 3↵
以文本方式显示
  1. 6↵
1秒 64M 0

二、题目翻译

        英文题目啊......翻成中文这事就交给你们手中的翻译软件了,我是说我先凝练一下题目在讲啥,它又要我们干啥。

首先为了方便,我这样描述一个木块:

a carpenter has received an order for a wooden directional,程序设计方法与实践2022,c++

        因为顶部和基只差一个单位长度,所以知道基就知道了顶部。也就是说要描述一个箭头长啥样,我只需要底部和基就行了。

题目向我们描述了这些信息:

①箭头和箭头是一块一块贴着搭上去的。

②从下往上搭的过程中,上面的箭头的底部,必须等于下面的箭头的底部,或者等于下面的箭头的基。

③相邻两个箭头需要有重叠部分,不然钉不住。

我们可以简单知道这些信息:

①相邻的两块箭头,因为上面的箭头的底部有两种可能放法,所以同样的数据自然可能有多种情况。

②题目就是要我们输出有多少种不同的情况。

题目输入共两行,第一行是木板的数量 n ,第二行的数据量为 n+1 ,其中第二行的第一个数据是最下面箭头的底部,之后的n个数据是第n-1行箭头的顶部。

题目要求输出可能的情况数%2147483647。


三、思路

这题难在......题目一开始看不懂。

看懂了以后,很容易想到递推。假设从下往上数第k块箭头的情况数为S(k),第(k+1)块箭头的情况数为S(k+1),S(k+1)和S(k)之间是有关系的。关键在于怎么计算S(k)。  


四、代码实现

注意几个点:

①假设 f[i][j] 是从下往上数第 i 块箭头,底部为 j 的情况数,显然S(i) = a carpenter has received an order for a wooden directional,程序设计方法与实践2022,c++

②第一块箭头的底部和顶部都已经确定,只有一种情况。

③当 i ≥ 2 时,第 i 块箭头的底部可能有 i 种情况,它们就是Input第二行的前 i 个数。

④鉴于 f[i][j] 可能会非常大(大到超过了2147483647),每一次最好都求一次余。

⑤懒得搞公式了,借用讨论区一张图

a carpenter has received an order for a wooden directional,程序设计方法与实践2022,c++

不清楚本人是否愿意被知晓名字,先不写。

限于博主的表达能力有限,这些个东西靠你们自己悟吧~


五、完整代码

#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
const int N = 2010;
ll f[N][N];    //f[i][j]表示第i个箭头,当底部为j的时候,可能的情况数。
int nd[N];    
//因为end存在关键字重复,这里写的是nd。nd[0]是最下面那一块的底部,之后nd[i]表示第i块的顶部

int n;
 
int main(){

	memset(f,0,sizeof(f));

	scanf("%d",&n);
	for (int i=0;i<=n;i++) {
		scanf("%d",&nd[i]);
	}
   
	f[1][nd[0]] = 1;     //第一块只有一种情况
	
	for (int i=2;i<=n;i++) { 
        //第i块

		for (int p=0;p<=i;p++) {
			int j = nd[p];
			if ( (j<nd[i]&&j<nd[i-1]) || (j>nd[i]&&j>nd[i-1]) ) {
				f[i][j] = f[i-1][j];
			}
			else if (j==nd[i-1]) {
				if (j<nd[i]) {
					for (int k=j+1;k<=n+1;k++) {
						f[i][j] += f[i-1][k];
					}
				}
				else {
					for (int k=1;k<=j-1;k++) {
						f[i][j] += f[i-1][k];
					}
				}
			}
			else f[i][j]=0;
			f[i][j] %= 2147483647;
		}

	}
	
	ll ans=0;
    
    //求第n块木板的情况总数
	for (int i=1;i<=n+1;i++) {
		ans += f[n][i];
		ans %= 2147483647;
	}
	cout << ans << endl;
	
	 
	return 0;
}

啧啧啧,这篇质量不高,看个乐呵就行。 文章来源地址https://www.toymoban.com/news/detail-732434.html

到了这里,关于方向标 | c++ | 动态规划的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C++ 一维动态规划

    PS:以下代码由C++实现 1.第N个泰波那契数  力扣 泰波那契序列 Tn 定义如下: T0 = 0, T1 = 1, T2 = 1, 且在 n = 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2 给你整数 n,请返回第 n 个泰波那契数 Tn 的值。 示例 1: 输入:n = 4 输出:4 解释: T_3 = 0 + 1 + 1 = 2 T_4 = 1 + 1 + 2 = 4 示例 2: 输入:n = 25 输出:

    2024年02月16日
    浏览(31)
  • 【算法思维】-- 动态规划(C++)

    OJ须知: 一般而言,OJ在1s内能接受的算法时间复杂度:10e8 ~ 10e9之间 (中值5*10e8) 。在竞赛中, 一般认为计算机1秒能执行 5*10e8 次计算 。 时间复杂度 取值范围 o(log2n) 大的离谱 O(n) 10e8 O(nlog(n)) 10e6 O(nsqrt(n))) 10e5 O(n^2) 5000 O(n^3) 300 O(2^n) 25 O(3^n) 15 O(n!) 11 时间复杂度排序: o(1

    2024年02月02日
    浏览(50)
  • 【C++刷题】动态规划

    这里我先声明一下dp问题的做题方法: 1.确定状态表示 2.确定状态方程 3.处理初始化问题(一般是下标的映射或者初始化保证填表正确) 4.确定填表顺序 5.根据状态表示确定返回值。 链接:点此进入 状态表示:以 i 位置为结尾的第i个斐波那契数。 状态转移方程:dp[i] = dp[i-1]

    2024年02月09日
    浏览(38)
  • Elasticsearch 8.0报错:received plaintext http traffic on an https channel, closing connection

    ES配置启动成功了,就是客户端访问服务端出现这个错误 原因 :是因为ES8默认开启了 SSL 认证。 因为 SSL 需要使用https方式请求,所以有以下两种解决办法: 1、使用 https 发送请求,即:把 http 请求改成 https 即可。 2、修改配置文件,需要修改配置文件则继续往下看。 修改

    2024年02月11日
    浏览(49)
  • 蓝桥杯(路径 动态规划 C++)

     思路: 1、利用动态规划的思想。 2、用f[i]来记录从第一个点到第i个点的最短距离。 3、f[i]赋值分两种情况,第一种:f[i]为0的时候,也就是第一种刚到i点的情况,记录其距离为最小公倍数;第二种:f[i]已经有值了,比较新的点到其距离和之前点到其距离,取小的赋值。

    2024年02月07日
    浏览(38)
  • C++ 动态规划 01背包问题

    有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 i 件物品的体积是 vi ,价值是 wi 。 求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。 输出最大价值。 输入格式 第一行两个整数, N,V ,用空格隔开,分别表示物品数量和背

    2024年04月27日
    浏览(41)
  • 动态规划:子序列问题(C++)

    动态规划往期文章: 动态规划入门:斐波那契数列模型以及多状态 动态规划:路径和子数组问题 1.最长递增子序列(中等) 链接 :最长递增子序列 题目描述 做题步骤 状态表示 对于线性dp,我们通常采用下面两种表示: (1)以某个位置为结尾,…… (2)以某个位置为起点,……

    2024年02月08日
    浏览(46)
  • C++动态规划模板汇总大全

    如果你不太了解dp(动态规划)是个什么东西,请回到上次dp。 链接:动态规划算法详解 【题目描述】 观察下面的数字金字塔。写一个程序查找从最高点到底部任意处结束的路径,使路径经过数字的和最大。每一步可以从当前点走到左下方的点也可以到达右下方的点。 在上

    2024年02月06日
    浏览(34)
  • 【c++】动态规划(dp)框架

    动态规划(Dynamic Programming)是解决计算问题的一种方法,通常用于解决优化问题和涉及重叠子问题的计算问题。它的核心思想是通过将问题分解为更小的子问题来求解,并且记忆化子问题的解,避免重复计算,从而提高效率。下面详细解释动态规划以及优化方法,并提供一个

    2024年02月03日
    浏览(45)
  • c++ 旅行商问题(动态规划)

      TSP,即旅行商问题,又称TSP问题(Traveling Salesman Problem),是数学领域中著名问题之一。   假设有一个旅行商人要拜访N个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所

    2024年02月03日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包