首页 / HTML / CodeforcesRound#274(Div.2)E题：RidinginaLift（DP）_html/css_WEB-ITnose

CodeforcesRound#274(Div.2)E题：RidinginaLift（DP）_html/css_WEB-ITnose

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了CodeforcesRound#274(Div.2)E题：RidinginaLift（DP）_html/css_WEB-ITnose，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1456字，纯文字阅读大概需要3分钟。

内容图文

题目地址：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;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(j<b)                {                    dp[j]=(sum[i+1&1][(j+b-1)/2]+mod-dp[j])%mod;                }                else if(j>b)                {                    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;}

内容总结

以上是互联网集市为您收集整理的CodeforcesRound#274(Div.2)E题：RidinginaLift（DP）_html/css_WEB-ITnose全部内容，希望文章能够帮你解决CodeforcesRound#274(Div.2)E题：RidinginaLift（DP）_html/css_WEB-ITnose所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/398880.html

来源：【匿名】