Codeforces Round #274 (Div. 2) E题：Riding in a Lift（DP）_html/css_WEB-ITnose

php中文网

发布时间：2016-06-24 11:56:02

1411人浏览过

来源于php中文网

原创

题目地址：http://codeforces.com/contest/479/problem/e

这题的动态转移方程很好想，但是最显然的是k*n*n的复杂度，明显不可以。于是就想到了用线段树来维护DP信息，但是仅仅k*n就已经濒临TLE了。。在加上个log就会TLE了，于是也不行。上网搜了一下才发现用个前缀和的小技巧就可以。= =！用了好多次了居然没有想到。。。。智商捉急。。于是剩下的就很简单了。

本来还想着，不可能走到b的另一侧，于是就只算一侧就可以了。。但是写起来才发现。。只算一侧还不如两侧一块算的代码短。。于是就一块算了。

代码如下：

帮衣帮-AI服装设计

AI服装设计神器，AI生成印花、虚拟试衣、面料替换

下载

立即学习“前端免费学习笔记（深入）”；

#include #include #include #include #include #include #include #include #include #include #include using namespace std;#define LL __int64const LL mod=1e9+7;LL dp[6000], sum[3][6000];int main(){    LL n, a, b, k, i, j;    while(scanf("%I64d%I64d%I64d%I64d",&n,&a,&b,&k)!=EOF)    {        memset(dp,0,sizeof(dp));        memset(sum,0,sizeof(sum));        dp[a]=1;        for(i=a;i<=n;i++)            sum[0][i]=1;        for(i=1;i<=k;i++)        {            sum[i&1][0]=0;            for(j=1;j<=n;j++)            {                if(jb)                {                    dp[j]=(sum[i+1&1][n]+mod-sum[i+1&1][(j+b)/2]+mod-dp[j])%mod;                }                sum[i&1][j]=(sum[i&1][j-1]+dp[j])%mod;                //printf("%I64d ",dp[j]);            }            //puts("");        }        printf("%I64d\n",sum[k&1][n]);    }    return 0;}

立即学习“前端免费学习笔记（深入）”；

HTML速学教程(入门课程)

HTML怎么学习？HTML怎么入门？HTML在哪学？HTML怎么学才快？不用担心，这里为大家提供了HTML速学教程(入门课程)，有需要的小伙伴保存下载就能学习啦！

下载

本站声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn

上一篇：在一个div中有许多图片，所有小图片都要显示在大图片上方，如何用css精确定位小图片的位置呢？效果图如下_html/css_WEB-ITnose 下一篇：ASP服务器错误提示乱码_html/css_WEB-ITnose

热门AI工具

DeepSeek

幻方量化公司旗下的开源大模型平台

AI 编程开发 AI 聊天问答

豆包大模型

字节跳动自主研发的一系列大型语言模型

AI 编程开发 AI大模型

通义千问

阿里巴巴推出的全能AI助手

AI 编程开发 Agent智能体

腾讯元宝

腾讯混元平台推出的AI助手

文档处理 AI 聊天问答

文心一言

文心一言是百度开发的AI聊天机器人，通过对话可以生成各种形式的内容。

AI 编程开发 AI 文本写作

讯飞写作

基于讯飞星火大模型的AI写作工具，可以快速生成新闻稿件、品宣文案、工作总结、心得体会等各种文文稿

AI 文本写作中文写作

即梦AI

一站式AI创作平台，免费AI图片和视频生成。

图片拼接

ChatGPT

最最强大的AI聊天机器人程序，ChatGPT不单是聊天机器人，还能进行撰写邮件、视频脚本、文案、翻译、代码等任务。

AI 编程开发 AI 文本写作

智谱清言 - 免费全能的AI助手

AI 编程开发 Agent智能体

相关专题

全国统一发票查询平台入口合集

本专题整合了全国统一发票查询入口地址合集，阅读专题下面的文章了解更多详细入口。

2026.02.03

短剧入口地址汇总

本专题整合了短剧app推荐平台，阅读专题下面的文章了解更多详细入口。

2026.02.03

植物大战僵尸版本入口地址汇总

本专题整合了植物大战僵尸版本入口地址汇总，前往文章中寻找想要的答案。

2026.02.03

c语言中/相关合集

本专题整合了c语言中/的用法、含义解释。阅读专题下面的文章了解更多详细内容。

2026.02.03

漫蛙漫画网页版入口与正版在线阅读漫蛙MANWA官网访问专题

本专题围绕漫蛙漫画（Manwa / Manwa2）官网网页版入口进行整理，涵盖漫蛙漫画官方主页访问方式、网页版在线阅读入口、台版正版漫画浏览说明及基础使用指引，帮助用户快速进入漫蛙漫画官网，稳定在线阅读正版漫画内容，避免误入非官方页面。

2026.02.03

Yandex官网入口与俄罗斯搜索引擎访问指南 Yandex中文登录与网页版入口

本专题汇总了俄罗斯知名搜索引擎 Yandex 的官网入口、免登录访问地址、中文登录方法与网页版使用指南，帮助用户稳定访问 Yandex 官网，并提供一站式入口汇总。无论是登录入口还是在线搜索，用户都能快速获取最新稳定的访问链接与使用指南。

114

2026.02.03

Java 设计模式与重构实践

本专题专注讲解 Java 中常用的设计模式，包括单例模式、工厂模式、观察者模式、策略模式等，并结合代码重构实践，帮助学习者掌握如何运用设计模式优化代码结构，提高代码的可读性、可维护性和扩展性。通过具体示例，展示设计模式如何解决实际开发中的复杂问题。

2026.02.03

C# 并发与异步编程

本专题系统讲解 C# 异步编程与并发控制，重点介绍 async 和 await 关键字、Task 类、线程池管理、并发数据结构、死锁与线程安全问题。通过多个实战项目，帮助学习者掌握如何在 C# 中编写高效的异步代码，提升应用的并发性能与响应速度。

2026.02.03

Python 强化学习与深度Q网络（DQN）

本专题深入讲解 Python 在强化学习（Reinforcement Learning）中的应用，重点介绍深度Q网络（DQN）及其实现方法，涵盖 Q-learning 算法、深度学习与神经网络的结合、环境模拟与奖励机制设计、探索与利用的平衡等。通过构建一个简单的游戏AI，帮助学习者掌握如何使用 Python 训练智能体在动态环境中作出决策。

2026.02.03

热门下载

网站特效

网站源码

网站素材

前端模板