Skip to content

S2OJ - 1470. 饥饿的小鸟

题解717 字
检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

题面

题目描述

一群饥饿的小鸟,要到河对岸吃东西。河的宽度为 NN 米,小鸟每飞行 LL 米就必须在一片荷叶上休息一下,才能够继续飞行。当然,小鸟们也可以选择没飞够 LL 米就先休息一下,但不能一次飞超过 LL 米。距离小鸟们出发的河岸一侧距离为 ii 的荷叶共有 AiA_i 片,每片荷叶在有小鸟停于上方休息后,就会沉入水底,不能够再供其他小鸟休息。

现在想要知道,至多有多少只小鸟能够抵达对岸。

输入格式

第一行输入两个整数 N,LN, L,含义见题面描述。 接下来一行 N1N-1 个整数 AiA_i,表示距离河的出发一侧距离为 ii 的荷叶的片数。

输出格式

输出一行一个整数,表示至多能够抵达前线的小鸟数量。

输入输出样例

样例输入 #1

10 5
0 0 1 0 2 0 0 1 0

样例输出 #1

3

样例解释 #1

三只小鸟可以分别走 05100 → 5 → 1005100 → 5 → 10038100 → 3 → 8 → 10

样例输入 #2

10 3
1 1 1 1 2 1 1 1 1

样例输出 #2

3

样例解释 #2

三只小鸟可以分别走 0147100 → 1 → 4 → 7 → 100258100 → 2 → 5 → 8 → 100369100 → 3 → 6 → 9 → 10

数据范围与约定

对于 20%20\% 的数据,L=N1L = N - 1
对于 50%50\% 的数据,1L<N51 \leq L < N \leq 50Ai30 \leq A_i \leq 3
对于 80%80\% 的数据,1L<N1001 \leq L < N \leq 1000Ai100 \leq A_i \leq 10
对于 100%100\% 的数据,1L<N1051 \leq L < N \leq 10^50Ai1040 \leq A_i \leq 10^4

思路

贪心。

尽可能使用当前点能达到的最远距离的承载容量,然后转移即可。

代码

#include <iostream>
#include <cstring>
#include <limits>
#include <queue>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 1e5 + 5;

int n, l, s, a[N], b[N];

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> l;

    for (int i = 1; i < n; i++) {
        cin >> a[i];

        s += a[i];
    }

    a[n] = b[0] = s;
    for (int i = 0; i < n; i++) {
        for (int j = std::min(i + l, n); j > i; j--) {
            if (b[j] < a[j]) {
                if (b[j] + b[i] <= a[j]) {
                    b[j] += b[i];
                    b[i] = 0;
                    break;
                } else {
                    b[i] -= a[j] - b[j];
                    b[j] = a[j];
                }
            }
        }
    }

    cout << b[n] << endl;

    return 0;
}