Codeforces 480C Riding in a Lift dp

简介:

主题链接:点击打开链接

意甲冠军:

特定 n a b k

构造一个长度k该序列。

使得序列中 对于随意两个相邻的数 | w[i-1] - w[i] | < | w[i] - b |

且第一个数 |a - w[1] | < | w[1] - b |

问:

有多少种不同的序列。


思路:dp

对于粗暴的dp复杂度是 n^3

我们能够用前缀和来优化掉一维的dp。。

反正是简单粗暴的题。详细看代码吧。。


#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
using namespace std;
typedef long long ll;
const int N = 5005;
const ll mod = 1000000007;
int a, b, K, n;
ll dp[N][N], sum[N];
void put(int k){
    printf("%d:", k);
    for(int i = 1; i <= n; i++)pt(dp[k][i]),putchar(' '); puts("");
}
ll solve(){
    dp[0][a] = 1;
    for(int k = 1; k <= K; k++)
    {
        sum[0] = 0;
        for(int i = 1; i <= n; i++) {
            sum[i] = sum[i-1] + dp[k-1][i];
            if(sum[i] >= mod) sum[i] -= mod;
        }
        for(int i = 1, j; i <= n; i++)
        {
            if(i==b)continue;
            j = (b+i)>>1;
            if(i < b)
            {
                if(b-j <= j-i) j--;
                dp[k][i] = sum[j] - dp[k-1][i];
            }
            else
            {
                if(j-b <= i-j) j++;
                dp[k][i] = sum[n] - sum[j-1] - dp[k-1][i];
            }
            if(dp[k][i] < 0){
                dp[k][i] %= mod;
                dp[k][i] += mod;
            }
        }

    }
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        ans += dp[K][i];
        if(ans >= mod) ans -= mod;
    }
    return ans;
}
int main() {
    while(cin>>n>>a>>b>>K){
        memset(dp, 0, sizeof dp);
        cout<<solve() % mod<<endl;
    }
    return 0;
}


版权声明:本文博客原创文章,博客,未经同意,不得转载。





本文转自mfrbuaa博客园博客,原文链接:http://www.cnblogs.com/mfrbuaa/p/4685004.html,如需转载请自行联系原作者


相关文章
codeforces 289 B. Polo the Penguin and Matrix
题目意思是在n*m的矩阵中,你可以对矩阵中的每个数加或者减d,求最少的操作次数,使得矩阵中所有的元素相同。 虽然在condeforces中被分到了dp一类,但完全可以通过排序,暴力的方法解决。
44 0
codeforces118——D. Caesar‘s Legions(DP)
codeforces118——D. Caesar‘s Legions(DP)
90 0
codeforces118——D. Caesar‘s Legions(DP)
LeetCode 59. Spiral Matrix II
给定正整数n,以螺旋顺序生成填充有从1到n2的元素的方阵。
95 0
【1105】Spiral Matrix (25分)【螺旋矩阵】
【1105】Spiral Matrix (25分)【螺旋矩阵】 【1105】Spiral Matrix (25分)【螺旋矩阵】
125 0
|
Java 索引 Python
Leetcode 54:Spiral Matrix 螺旋矩阵
54:Spiral Matrix 螺旋矩阵 Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order. 给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。
831 0