Algoogle

Algorithm for Programming Contest

JOI 春合宿 2010 Stairs

Category: JOI Tag: dp

Stairs

問題概要


段差の高さがそれぞれ異なる階段がある.
高さpまで一度に段差を登れるとき, 一番下から上まで登る方法は何通りあるか

解法


DPする.
ある段差iについて, 高さの総和がp以下になる最長の区間[l,i)の場合の数の総和が段差iを登り終わった時までの登り方の総数.
区間の高さの和は右端をiまで伸ばして左端を高さの合計がp以下になるまで縮めていけば良い.
区間の総和を適当に保存しておけばよい.

コード


(Stairs.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;
const int mod = 1234567;
long long n, p, h[500010], sum[500010];

int solve()
{
        sum[1] = 1;
        int l = 0, r = 0;
        long long hs = 0;
        for (int i = 0; i < n; i++) {
                while(r <= i) hs += h[r++];
                while(l < r and p < hs) hs -= h[l++];
                sum[r+1] = (sum[r]+(sum[r]-sum[l])%mod+mod)%mod;
        }
        return ((sum[n+1]-sum[n])%mod+mod)%mod;
}

void input()
{
        cin >> n >> p;
        for (int i = 0; i < n; i++) cin >> h[i];
}

int main()
{
        cin.tie(0);
        cin.sync_with_stdio(0);
        input();
        cout << solve() << endl;
        return 0;
}

Comments