首页 > 其他分享 >2320. 统计放置房子的方式数

2320. 统计放置房子的方式数

时间:2024-04-15 22:58:58浏览次数:32  
标签:方案 2320 地块 int 房子 放置 一侧

题目链接:

本题和198.打家劫舍有异曲同工之妙。

由于街道两侧互不干扰,因此可以考虑只计算出一侧的状态,然后利用乘法原理即可。

状态划分时,考虑第 \(i\) 个地块选或不选:

  • 若选,则第 \(i-1\) 个地块不能选,第 \(i - 2\) 个地块可选可不选。\(f[i]=f[i-2]\)
  • 若不选,则第 \(i-1\) 个地块可选可不选,\(f[i]=f[i-1]\)。
class Solution {
public:
    int countHousePlacements(int n) {
        const int MOD = 1e9 + 7;
        vector<int> f(n + 1);//f[i]表示街道的一侧前i个地块放置房屋的方案数
        f[0] = 1;//空着,一种方案
        f[1] = 2;//空或不空,两种方案
        for (int i = 2; i <= n; i++) {
            f[i] = (f[i - 1] + f[i - 2]) % MOD;
        }
        return (long long)f[n] * f[n] % MOD;//注意这里f[n]*f[n]可能会溢出,需要用long long隐式转换一下
    }
};

标签:方案,2320,地块,int,房子,放置,一侧
From: https://www.cnblogs.com/pangyou3s/p/18137084

相关文章

  • 2-34. 绘制房子和可以被砍伐的树
    绘制房子首先将房子的下半部分绘制到GroupTop这层然后把房顶绘制到Front1这层绘制碰撞层可以被砍伐的树其中Tree01_Bottom是有阴影的树根,Tree01_Trunk是没有阴影的树根调整树根的锚点接着把树的上部分连接上去把树根和树干放到同一个父物体下面树遮挡人......
  • 2024-04-03:用go语言,在一个小城市里,有 m 个房子排成一排, 你需要给每个房子涂上 n 种颜
    2024-04-03:用go语言,在一个小城市里,有m个房子排成一排,你需要给每个房子涂上n种颜色之一(颜色编号为1到n),有的房子去年夏天已经涂过颜色了,所以这些房子不可以被重新涂色,我们将连续相同颜色尽可能多的房子称为一个街区。比方说houses=[1,2,2,3,3,2,1,1],它包含5个街......
  • 算法---动态规划练习-9(粉刷房子)
    题目1.题目解析2.讲解算法原理3.编写代码1.题目解析题目地址:点这里2.讲解算法原理创建dp表:vector<vector>dp(n,vector(3))。这里创建了一个二维向量dp,其中dp[i][j]表示第i天选择颜色j的最小成本。初始化第一天的成本:for(inti=0;i<3;i++)......
  • 你真的了解回调函数吗?(文章最后放置源码)
    一、什么是回调函数简单来说就是通过函数指针调用的函数。复杂一些呢就是说将函数的指针(地址)作为参数传递给另外一个函数使用,当这个指针被用来调用其指向的函数的时候被调用的函数就是回调函数。二、回调函数怎么使用1、在学习回调函数之前我们是如何进行运算的我们来看下......
  • 男朋友在飞书被裁了,去年刚贷款在上海买了房子,每月房贷+房租就要1.2w,怎么办?
    作者|周天编辑|豆奶“飞书裁人”的消息传开后,很多社交平台的朋友都在讨论。毕竟在当下特殊时期,找工作不易,但裁人更难。更何况是大厂字节的飞书,这下很多人都悬了心。在社交媒体上,有不少网友已经在讨论这件事了。有的人才入职两个月,就已经接到通知了;有的人生怕被选中,正处于......
  • 洛谷 P9237 [蓝桥杯 2023 省 A] 像素放置
    题意:n*m的方格,有的格子是数字,是数字的格子代表了相邻(包括自己)的9个格子内颜色值为1的格子有这么多个。给出这个方格,求满足条件的颜色方格,保证答案唯一。n<=10,m<=10。思路:想不出好办法,直接暴力+剪枝。暴力好说,01dfs即可,关键是如何剪枝。剪枝肯定是已经不会再变动颜色的......
  • .NET分布式Orleans - 3 - Grain放置
    在Orleans7中,Grain放置是指确定将Grain对象放置在Orleans集群中的哪些物理节点上的过程。Grain是Orleans中的基本单位,代表应用程序中的逻辑单元或实体。Grain放置策略是一种机制,用于根据不同的因素,将Grain对象放置在合适的节点上,以实现负载均衡、最小化网络延迟和提高容错性。G......
  • 房子种类
    1、根据楼层高度低层:低层房屋是指高度不超过10米的建筑物,一般是13层建筑物,如平房、别墅等。多层:多层房屋指高于10米且不超过24米的建筑物。多层房屋一般为48层。小高层:一般把812层或13层的建筑称为“小高层”高层:14层及以上的建筑。2、根据建筑形式板楼:户型是南北或东西通透......
  • P3957 [NOIP2017 普及组] 跳房子
    原题链接题解二分加动态维护区间最大值注意设立变量的含义,改变变量值的规则code#include<bits/stdc++.h>#definelllonglongusingnamespacestd;llsum[500005]={0};structunit{llx,v;booloperator<(constunit&b)const{returnb.v>v;}//}room[5000......
  • 将 Redis 数据放置在 Controller 层还是 Service 层
    在三层架构中,将Redis数据放置在Controller层还是Service层,同样需要根据具体的业务需求和设计原则来决定。以下是一些常见的考虑因素:数据访问频率:如果某个数据在多个请求之间频繁被读取或写入,可以考虑将其放置在Service层的缓存中,以减少对Redis的频繁操作。这样可以提高......