[HG]小G坐电梯 题解
2024-10-07 02:24:30
C 小G坐电梯
题目描述
小G来到了著名的某大厦。大厦一共有n层,初始的时候小G在第 A 层。
小G特别想去B层小 M 的办公室看一看,然而因为安保原因,B层已经被封锁无法进入。
但是小G既然来了,就想在大厦里面逛一逛。大厦里面有一部电梯,小G决定坐 k 次电梯。
因为小G比较无聊,他给自己设定了这样一个规矩:假如当前他在x层,则他要去的下一个楼层y和x的楼层差必须要小于 x 和 B 的楼层差,即 \(|x−y| < |x−B|\) 。
每到达一个楼层,小G都要记录下来其楼层号。
当小G转完一圈后,他也记录下了 \(k + 1\) 个楼层号(可能有重复)。
小G现在 想知道,按照他定下的规矩,一共有多少种可能的楼层号序列?
题解
定义f[i][j][k]为当前走了i步,距离终点为j的,方向为k(0向下,1向上)。
暴力DP+前缀和,滚动数组压掉一维。
代码
#include <cstdio>
#include <cmath>
using namespace std;
#define max(a,b) ((a>b)?a:b)
const int MOD = 1e9 + 7;
//k dlt lft 0:dwn, 1:up
long long f[10005][2];
long long pre[20005][2];
int mx_dlt, dlt;
inline long long pls(long long a, long long b){
return ((a + b >= MOD) ? (a + b - MOD) : (a + b));
}
inline void getPre(){
pre[0][0] = pre[0][1] = 0;
for (int j = 1; j <= mx_dlt; ++j){
pre[j][0] = pls(pre[j - 1][0], f[j][0]);
pre[j][1] = pls(pre[j - 1][1], f[j][1]);
}
for (int j = mx_dlt + 1; j <= mx_dlt * 2; ++j){
pre[j][0] = pre[j - 1][0];
pre[j][1] = pre[j - 1][1];
}
}
int main(){
freopen("lift.in", "r", stdin);
freopen("lift.out", "w", stdout);
int n, A, B, k; scanf("%d %d %d %d", &n, &A, &B, &k);
mx_dlt = max(B * 2, abs(n - B) * 2); dlt = abs(A - B);
f[dlt][0] = (A < B), f[dlt][1] = (A > B);
getPre();
for (int i = 1; i <= k; ++i){
for (int j = 1; j <= mx_dlt; ++j){
int tmp0 = f[j][0], tmp1 = f[j][1];
if (B - j > 0)
f[j][0] = ((pre[mx_dlt][0] - pre[j / 2][0] - tmp0) % MOD + MOD) % MOD;
if (B + j <= n)
f[j][1] = ((pre[mx_dlt][1] - pre[j / 2][1] - tmp1) % MOD + MOD) % MOD;
}
getPre();
}
long long ans = (pre[mx_dlt][0] + pre[mx_dlt][1] + MOD * 2) % MOD;
printf("%lld", ans);
return 0;
}
最新文章
- ABP(现代ASP.NET样板开发框架)系列之23、ABP展现层——异常处理
- 链接的热键属性accesskey
- NOIP2005 等价表达式
- 【Android测试】【第十五节】Instrumentation——官方译文
- Quartz 基本概念及原理
- window.opener强大功能
- sql 批量操作(存在的更新,不存在的插入)
- Objective-C ,ios,iphone开发基础:几个常用类-NSString
- DB2数据库实例创建与删除 学习笔记
- 学习笔记——Java数字处理类
- C#Winform使用mysql作为本地数据库
- 【Luogu1345】周游加拿大(动态规划)
- 在Centos7.2(64位)下搭建Web服务器
- 常用的settings.xml文件
- 算法进阶面试题01——KMP算法详解、输出含两次原子串的最短串、判断T1是否包含T2子树、Manacher算法详解、使字符串成为最短回文串
- C++二级指针第一种内存模型(指针数组)
- android adb介绍
- Android中的动画,选择器,样式和主题的使用
- saltstack plug in
- shell入门-grep过滤-1