首页 > 代码库 > Codeforces Round #274 Div.1 C Riding in a Lift --DP

Codeforces Round #274 Div.1 C Riding in a Lift --DP

题意:给定n个楼层,初始在a层,b层不可停留,每次选一个楼层x,当|x-now| < |x-b| 且 x != now 时可达(now表示当前位置),此时记录下x到序列中,走k步,最后问有多少种可能的数的序列.

解法:

定义:      dp[i][j] 表示第i步在j楼的不同序列的个数

转移方程: 当j<b时, 那么dp[i][j] += dp[i-1][0~(j与b的中点(以下))]

               当j>b时, 那么dp[i][j] += dp[i-1][(j与b的中点(以下))~n]

由于dp[i][j]的值只跟dp[i-1][]的一些值有关,所以用滚动数组会大大减小内存。

用一个sum[i][j]维护前缀和即可。

代码:

#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>#define Mod 1000000007#define lll __int64using namespace std;#define N 100007lll dp[2][5002],sum[2][5002];int n;int main(){    int a,b,k,i,j;    while(cin>>n>>a>>b>>k)    {        memset(dp,0,sizeof(dp));        memset(sum,0,sizeof(sum));        dp[0][a] = 1LL;        for(i=a;i<=n;i++)            sum[0][i] = 1LL;        int now = 0;        for(i=1;i<=k;i++)        {            now ^= 1;            memset(dp[now],0,sizeof(dp[now]));            memset(sum[now],0,sizeof(sum[now]));            for(j=1;j<=n;j++)            {                if(j < b)                {                    int k = (j+b-1)/2;                    dp[now][j] = (dp[now][j]+sum[now^1][k]-dp[now^1][j])%Mod;                }                else if(j > b)                {                    int k = (j+b+2)/2;                    dp[now][j] = (dp[now][j]+sum[now^1][n]-sum[now^1][k-1]-dp[now^1][j])%Mod;                }                sum[now][j] = (sum[now][j-1]+dp[now][j])%Mod;            }        }        lll sum = 0;        for(i=1;i<=n;i++)            sum = (sum+dp[now][i])%Mod;        cout<<(sum+Mod)%Mod<<endl;    }    return 0;}
View Code

 

Codeforces Round #274 Div.1 C Riding in a Lift --DP