FZU Problem 2156 Climb Stairs DP
2024-10-01 11:21:05
http://acm.fzu.edu.cn/problem.php?pid=2156
题目大意:
爬楼梯,要爬到n这个位置,每次可以走x也可以走y,然后一定要经过A和B两点,求最终到达n的方案数。
思路:
昨天FZU月赛题,今天小伙伴问我的- -|||,晚上回来敲完,发现有校!!选!!!课!!!!!哭
因为一定要到达A和B,那么直接分成0~A,A~B,B~N递推就好了。
注意每次不要越界,比如0~A,那么不要超过A。因为你可能超过A,没有到A,对后面的累加有影响。(结果偏大)
详见代码。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=10000+10;
const int mod=1000000007;
__int64 f[MAXN];
int n,x,y,a,b;
void solve(int L,int R)
{
for(int i=L;i<=R;i++)
{
if(i+x<=R)
f[i+x]=(f[i]+f[i+x])%mod;
if(i+y<=R)
f[i+y]=(f[i]+f[i+y])%mod;
}
}
int main()
{
while(~scanf("%d%d%d%d%d",&n,&x,&y,&a,&b))
{
memset(f,0,sizeof(f));
if(a>b) swap(a,b);
f[0]=1;
solve(0,a);
solve(a,b);
solve(b,n);
printf("%I64d\n",f[n]%mod);
}
return 0;
}
最新文章
- 借助node实战WebSocket
- windows programming can&#39;t find windows.h
- Java-数组练习2
- [python]用Python进行SQLite数据库操作
- IIS Shared Configuration
- Hdu3640-I, zombie(模拟+二分)
- [置顶] Jquery发展
- ASP.NET使用WebApi接口实现与Android客户端的交互(图片或字符串的接收与回传)
- Response ServletContext 中文乱码 Request 编码 请求行 共享数据 转发重定向
- linux(乌班图)修改apt下载源
- SpringBoot入门小案例
- 单KEY业务,数据库水平切分架构实践 | 架构师之路
- windows设置电脑的固定IP
- Hadoop视频教程汇总
- 安装好php后找不到php.ini
- streamsets 集成 cratedb 测试
- springboot-23-aspectj日志记录及threadlocal内存泄漏
- python Django Ajax基础
- jdk1.6 支持 tls1.2协议 并忽略身份验证
- hdu6134 Battlestation Operational 莫比乌斯第一种形式
热门文章
- 九度 题目1154:Jungle Roads
- IOS学习之斯坦福大学IOS开发课程笔记(第六课)
- Server.MapPath()的用法
- DG性能
- deep-in-es6(四)
- react-native React Native version mismatch
- Ansible学习记录一:Linux下部署
- newgrp---将当前登录用户临时加入到已有的组中
- 【Codeforces Round #426 (Div. 2) A】The Useless Toy
- 关于oracle sql语句查询时 表名和字段名要加双引號的问题具体解释