做网站i3够用吗,深圳新星公司官网,html5网站多少钱,网站备案制度题目
描述
一位木匠收到了一个木制指示牌的订单。每块木板必须与前一块垂直对齐#xff0c;要么与前一个箭头的基部对齐#xff0c;要么与相反的一侧对齐#xff0c;在那里用特制的螺钉固定。两块木板必须重叠。木匠将设计师发送的草图编码成了一个整数序列#xff0c;但…题目
描述
一位木匠收到了一个木制指示牌的订单。每块木板必须与前一块垂直对齐要么与前一个箭头的基部对齐要么与相反的一侧对齐在那里用特制的螺钉固定。两块木板必须重叠。木匠将设计师发送的草图编码成了一个整数序列但该序列不能确定唯一的模型他已经把原始草图扔掉了。这看起来像是一个微不足道的任务但对他来说却是一个巨大的拼图。 序列有1 N个元素将(N)个箭头从底部到顶部的位置进行编码。第一个元素是底部箭头左侧的位置。剩余的N个元素定义了箭头头部的起始位置从底部到顶部第i个元素是第i个箭头基部的位置。例如左侧和右侧的两个标志可以通过2 6 5 1 4进行编码。
由于木板必须与前一块垂直对齐要么与前一个箭头的基部对齐要么与相反的一侧对齐如果序列是2 6 5 1 4 3第五个箭头可以用一个螺钉固定在任何一个描绘的标志上在1指向右边或4指向左边箭头基座在3。
如果序列是2 3 1第二个箭头只能用一个螺钉固定在3上指向左边因为连续的木板必须重叠。 所有的箭头头部都是相似的设计师告诉木匠它们的基部站在不同的垂直线上底部箭头的左侧也是如此共同形成1..(N 1)的排列。这就是为什么木匠忽略了细节只是写下了排列例如2 6 5 1 4 3。
给定木匠写下的数字序列计算可以制作的指示牌数量。由于数字可能非常大你必须对2147483647取模。序列的第二个整数始终大于第一个整数底部的箭头总是指向右边。
输入
第一行有一个整数N第二行包含从1到N 1的整数的排列。同一行中的整数之间用一个空格分隔。
输出
输出一行其中包含给定排列描述的不同标志的数量对2147483647取模。
注意
1 ≤ N ≤ 2000 题意
只需关注箭头长方形部分的头部靠近三角形和底部。箭头从下往上依次放置。第一个箭头的头部和底部题目已经确定并且头部下标一定大于底部。上面的箭头的底部必须等于下面的箭头的底部或者等于下面的箭头的头部。相邻两个箭头需要有重叠部分即不能错开。
由此推知
对于当下箭头而言上一块箭头的头部和底部很重要。上面的箭头的底部可能有多种放法题目就是要我们输出有多少种不同的情况。要求对输出结果%2147483647。 思路动态规划
我们用数组s[N1]记录每一块木块的头部下标。注意s[0]存储第一块的底部下标 第一步确定dp数组以及下标的含义
我们需要一个二维dp数组dp[i][j]表示第i个箭头以j为底时的方案数。 第二步确定递推公式
3种情况
第i块的头比上一块的头和尾都小 dp[i][max(s[i - 1], s[j])] dp[i - 1][s[j]];第i块的头比上一块的头和尾都大 dp[i][min(s[i - 1], s[j])] dp[i - 1][s[j]]; 第i块的头在上一块头尾之间 dp[i][s[i - 1]] dp[i - 1][s[j]]; dp[i][s[j]] dp[i - 1][s[j]]; 第三步dp数组初始化
第一个箭头只有一种放的方法dp[1][s[1]]1
遍历每一个箭头时令dp[i][s[i]]1以本身头部为底时为一。结果记得减一。 第四步确定遍历顺序
外循环从第二个箭头开始内循环遍历上一个箭头所有可能底部。 如果dp[i-1][j]0,说明上一个箭头存在以该底部放置的方案方可进入递推。 第五步结果处理
遍历dp[N]把每一个底部的方案加起来就是结果。 注意事项
long long存储数据。最后结果和每次dp变化之后和要取模。 C完整代码
改改再提交乐学有查重
#include iostream
#include vector
using namespace std;const int MOD 2147483647;int main() {int N;cin N;vectorlong long s(N 1);for (int i 0; i N; i) {cin s[i];}vectorvectorlong long dp(N 1, vectorlong long(2001, 0));dp[1][s[0]] 1;dp[1][s[1]] 1;for (int i 2; i N; i) {for (int j i - 2; j 0; j--) {dp[i][s[i]] 1;if (dp[i - 1][s[j]] ! 0) {if (s[i] s[i - 1] s[i] s[j]) {dp[i][min(s[i - 1], s[j])] dp[i - 1][ s[j]];dp[i][min(s[i - 1], s[j])] % MOD;}else if (s[i] s[i - 1] s[i] s[j]) {dp[i][max(s[i - 1], s[j])] dp[i - 1][s[j]];dp[i][max(s[i - 1], s[j])] % MOD;}else if ((s[i] s[i - 1] s[i] s[j]) || (s[i] s[i - 1] s[i] s[j])) {dp[i][s[i - 1]] dp[i - 1][s[j]];dp[i][s[i - 1]] % MOD;dp[i][s[j]] dp[i - 1][s[j]];dp[i][s[j]] % MOD;}}}}long long res 0;for (int i 0; i 2000; i) {res dp[N][i];res % MOD;}cout res-1 endl;return 0;
}
