[gmoj 3505]【NOIP2013模拟11.4A组】积木

news/2024/4/16 2:46:21

在这里插入图片描述
思路:
水解:O( n 2 n^2 n2)

考虑转化问题,判断合法性。
经过推理,我们得知每一个变量和上一个至多相差 1 。上一个变量是 2 的话,这一个只能取 3 或者 2 或者 1 。
在这里插入图片描述
题目可以转化为这幅图,a和b代表两个确定高度,求:
从a开始,每次可以向右上/右/右下走,不能越过紫线,求到b点的方案数
因为相邻两块积木的高度 如果相差超过 2 22 的话,无法构造。(这点应该清楚)

然后我们就可以DP 来计算方案数了。
设f[i][j] 表示 已经处理完前 i−1 个数之后,当前 第i 个数 选择了j 高度 的合法方案数。
即按照它相邻两个数相差 ≤ 1 \le 1 1 的性质,我们即可推出下列柿子:(当 a i = − 1 a_i=-1 ai=1 时)
f [ i ] [ j ] = f [ i − 1 ] [ j − 1 ] + f [ i − 1 ] [ j ] + f [ i − 1 ] [ j + 1 ] f[i][j]=f[i-1][j-1]+f[i-1][j]+f[i-1][j+1] f[i][j]=f[i1][j1]+f[i1][j]+f[i1][j+1]
特别地,对于越界的访问(比如 j=1 或者j=num[i−1] )就不统计越界的答案。
a i > − 1 a_i>-1 ai>1时特判即可,不需要枚举j 。
最后这个 f 数组还要取模。

#include <cstdio>
#include <iostream>
#include <cstring>
#pragma GCC optimize(2)
#define ll long long
#define mod 1000000007using namespace std;const int N = 2e4 + 10;
int n, t, tt;
ll a[N], f[5][N];int h(int x)  //求出当前点最大可能的高度
{if(x < n / 2 + 1) return x - 1;return n - x;
}int main()
{freopen("brick.in", "r", stdin);freopen("brick.out", "w", stdout);scanf("%d", &n);for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);f[0][0] = 1;for(int i = 1; i <= n; i++){t = h(i);tt = h(i - 1);if(a[i] != -1){if(a[i] <= t){f[1][a[i]] += f[0][a[i]];if(a[i]> 0) f[1][a[i]] += f[0][a[i] - 1];if(a[i] < tt) f[1][a[i]] += f[0][a[i]+1];if(!(i % 10)) f[1][a[i]] %= mod;			}}else{for(int j = 0; j <= t; j++){f[1][j] += f[0][j];if(j >= 1) f[1][j] += f[0][j - 1];if(j < tt) f[1][j] += f[0][j + 1];if(!(i % 10)) f[1][j] %= mod;}}memcpy(f[0], f[1], sizeof(f[1]));memset(f[1], 0, sizeof(f[1]));}printf("%lld\n", f[0][0] % mod);return 0;
}

http://www.ppmy.cn/news/560780.html

相关文章

JZOJ 3505. 【NOIP2013模拟11.4A组】积木(brick)

3505. 【NOIP2013模拟11.4A组】积木(brick) (File IO): input:brick.in output:brick.out Time Limits: 1000 ms Memory Limits: 262144 KB Description 小A正在搭积木。有N个位置可以让小A使用&#xff0c;初始高度都为0。小A每次搭积木的时候&#xff0c;都会选定一个拥有…

【组合】BZOJ3505(Cqoi2014)[数三角形]题解

题目概述 求 nm 网格中的三角形个数。 解题报告 首先肯定是用总方案数 (n3) 减去不合法的方案数要方便很多。但是怎么求不合法&#xff08;三点共线&#xff09;的方案数&#xff1f; 有个结论是横长为 x 纵长为 y 的线段中整点的个数为 gcd(x,y)1 &#xff0c;yy一下不…

【HDOJ】3505 Writing Robot

挺好的一道题目&#xff0c;我的做法是kmpDinic网络流。kmp求子串在P中出现的次数&#xff0c;从而计算love值。网络流主要用来处理最优解。case2中p1的love值是8&#xff0c;p2的love值是7&#xff0c;最终T包含p1和p2&#xff0c;hate值也仅仅算一次。这个题目难点在于思考为…

【题解】【AcWing】3505. 最长ZigZag子序列

3505. 最长ZigZag子序列 原题传送&#xff1a;AcWing 3505. 最长ZigZag子序列 一个整数序列的子序列是指从给定序列中随意地&#xff08;不一定连续&#xff09;去掉若干个整数&#xff08;可能一个也不去掉&#xff09;后所形成的整数序列。 对于一个整数序列 x 1 , x 2 ,…

BZOJ3505 [Cqoi2014]数三角形

明显容斥。总答案减掉共线答案。共横线和共竖线简单。难点在于共斜线计数。 考虑暴力。枚举每个点对连线间整点数量&#xff0c;这些点可以作为共线的第三点&#xff0c;种数$gcd(x_1-x_2,y_1-y_2)-1$。 可以证明这是不重不漏的&#xff08;枚举且仅枚举到了每个点对作为共线两…

w3690 支持服务器内存,微星S20内存是什么

ThinkStation S20 工作中站 内存支持(普通台式机内存 DDR3 2R*8规格 800频率 1066频率 1333频率内存) 支持(纯ECC DDR3 2R*8 -800频率1066频率1333频率的内存) CPU支持 仅插满1到3个内存槽的CPU 800频率 内存支持 E5502 E5503 E5504 E5506 E5507 E5520 E5530 E5540 1066频率 内…

POJ 3505

题意&#xff1a;一个类似于硬磁盘的停车场&#xff0c;要从哪取车就让磁头转到哪然后让盘面旋转使得要取的车到磁头处&#xff0c;然后读取到信息回到出口处。。。然后给你取车顺序&#xff0c;问总花费时间。 题解&#xff1a;模拟吧。 View Code 1 #include<cstdio>2…

我理解的元宇宙,为什么游戏公司股价狂飙?

最近一段时间元宇宙特别火&#xff0c;各个游戏公司的股价一路上涨&#xff0c;我想说真TM操蛋&#xff0c;这都是什么事&#xff0c;这就上涨了&#xff1f;他们做了什么? 什么是元宇宙&#xff1f; “元宇宙”是沉浸式的虚拟空间&#xff0c;用户可在其中进行文化、社交、娱…

用计算机弹千鸟,火影:哪个忍术结印数量最多?千鸟6个,水龙弹之术44个,它:100...

首先就是螺旋丸了&#xff0c;不需要结印。火影中人气最高的一个忍术了&#xff0c;四代水门花了3年的时候创造了这个忍术&#xff0c;而且经过他和自来也的改良&#xff0c;成为了瞬发型的A级忍术。后来传到鸣人手上后才开始崭露头角&#xff0c;整部动漫下来鸣人靠着这个忍术…

C语言阿斯码,木叶四位上忍设定各不相同,网红负责秀操作,她只需要美就够了...

原标题&#xff1a;木叶四位上忍设定各不相同&#xff0c;网红负责秀操作&#xff0c;她只需要美就够了 木叶四位上忍设定各不相同&#xff0c;网红负责秀操作&#xff0c;她只需要美就够了 说道忍界网红&#xff0c;那一定就是卡卡西了。卡卡西在《火影》当中的表现俘获了大批…

机器人鸣人是哪一集_火影里的五个机器人,第一个比鸣人还厉害,机器丁次你都没见过...

火影虽然是一部讲述众多忍者们的热血故事&#xff0c;但是火影里的时代并不是和古代一样&#xff0c;里面的生活是和现在的我们一样&#xff0c;在动漫里的忍者也是住的高楼&#xff0c;随时打电话&#xff0c;生病了也要去医院&#xff0c;也会肚子饿&#xff0c;也要一天三顿…

懂商业的技术合伙人(10):伟大的乔帮主,从不滥用绝学'降龙十八掌'

致敬&#xff1a;谨以此文&#xff0c;献给伟大的乔帮主。乔帮主英雄神武&#xff0c;永远活在我们80后的心中。 太多的技术人员&#xff0c;总想在项目中使用牛逼炫丽的技术。 作为一名以“懂商业的技术合伙人”为目标的技术人&#xff0c;很有必要去探讨这个严肃的话题&…

从高考到程序员的成长之路

转载请注明作者和出处&#xff1a;http://blog.csdn.net/c406495762 征文系列之从高考到程序员 前言高中本科研究生 1 前言 风风雨雨四十载——高考恢复40年&#xff0c;中国士子的人生上升通道也已经被打通了40载。虽然社会的多元发展&#xff0c;已经淡化了“高考决定人生”…

程序猿们最该掌握的技术

不知道你看过火影忍者没&#xff08;没看过不影响&#xff09;&#xff0c;看过火影忍者的同学&#xff0c;觉得鸣人的最强忍术是什么呢&#xff1f;影分身&#xff0c;后宫之术&#xff0c;大玉螺旋丸&#xff0c;风遁手里剑&#xff1f;NO&#xff0c;NO&#xff0c;NO&#…

系统性能优化的十大策略(强烈推荐,建议收藏)

点击关注公众号&#xff0c;实用技术文章及时了解 上篇 提升系统性能&#xff0c;榨干计算机资源是程序员的极致追求&#xff0c;今天跟大家聊聊性能优化。分为上中下三篇&#xff0c;由浅及深的写了关于性能优化的方方面面&#xff0c;并不仅仅局限于代码层面&#xff0c;希望…

程序员最应该掌握的技术

不知道你看过火影忍者没&#xff08;没看过不影响&#xff09;&#xff0c;看过火影忍者的同学&#xff0c;觉得鸣人的最强忍术是什么呢&#xff1f;影分身&#xff0c;后宫之术&#xff0c;大玉螺旋丸&#xff0c;风遁手里剑&#xff1f;NO&#xff0c;NO&#xff0c;NO&#…

火影推荐程序连载82-80%的学校还在给新生上C语言,它们OUT了吗?

大家好&#xff0c;最近有小伙伴在后台问我&#xff0c;大一新生学校在教C语言&#xff0c;是不是已经过时了&#xff1f;第一门语言应该学什么比较好&#xff1f;大学期间什么课程对于毕业之后的从业帮助比较大呢&#xff1f; 今天这篇文章就和大家简单聊聊这个问题。 关于我…

火影150集碎片拾忆 记于2014-04-08

身边的朋友一直再给我推荐火影&#xff0c;飞哥&#xff0c;还有打工时结识的一个朋友。那几天一时兴起&#xff0c;就花了大概三天的时间看了150集&#xff0c;因为豆瓣评论又说150集之后已经大不如前了&#xff0c;就停在了这里&#xff0c;等以后有机会会再看。   在《火…

火影700话完结 15年完结大结局

火影忍者700话大结局更新了&#xff01;&#xff01;鸣人终于当上了火影&#xff0c;老婆是雏田&#xff0c;儿子叫博人&#xff0c;女儿叫日葵&#xff0c;佐助娶了小樱&#xff0c;女儿名字叫莎拉娜&#xff0c;鹿丸和手鞠结婚&#xff0c;儿子叫鹿代。   木叶丸当上了老师…

《火影忍者》名言录(2.27更新)

1、鸣人(鸣人第2集末对木叶丸说的)虽然会有各种各样不愉快的事&#xff0c;会有各种各样令人迷茫的事&#xff0c;但我还是好不容易让一个人认可了我&#xff0c;不过光是这样就已经花了我好多的工夫。想要得到大家的认可&#xff0c;取得火影这个厉害的头衔的话&#xff0c;那…
最新文章