程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Codeforces 480C Riding in a Lift dp

Codeforces 480C Riding in a Lift dp

編輯：C++入門知識

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 
#include 
#include 
#include 
#include 
#include 
#include 
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<