PHP8.1.21版本已发布
vue8.1.21版本已发布
jquery8.1.21版本已发布
首页
课程
路径
文章
PHP培训
精品课
下载

技术文章  >  web前端 > html教程

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

原创
2016-06-24 11:56:02 1025浏览

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

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

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

代码如下：

#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;ib)                {                    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;}


Codeforces Round #274 (Div. 2) E题：Riding in a Lift（DP）PHP课程HTML视频教程CSS视频JS视频教程Vue视频教程
声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn核实处理。
上一条：在一个div中有许多图片，所有小图片都要显示在大图片上方，如何用css精确定位小图片的位置呢？效果图如下_html/css_WEB-ITnose 下一条：ASP服务器错误提示乱码_html/css_WEB-ITnose

相关文章

查看更多
  • 热门课程
打开APP，随时随地在线学习！