a693: 吞食天地

內容

好餓歐歐歐歐

有 n 個食物在你面前排成一排

每個食物有它的飽足度

你想知道把其中一段通通吃掉會獲得多少飽足度

輸入

多組測資以 EOF 結束

每組測資開始有兩個正整數 n,m (n,m <= 100000)

接下來一行有 n 個不超過一千的正整數依序代表每個食物的飽足度

接下來 m 行每行有兩個數字 l,r (1 <= l <= r <= n)

代表你想要吃掉第 l 個到第 r 個食物

3 3
1 2 3
1 3
1 2
2 3

輸出

對每組測資輸出 m 行，代表總飽足度

6
3
5

解題思路

基礎 DP 題，由於從 A 吃到 B 時不會有中間某個不吃的情況，所以總飽足度陣列可以儲存從零到該項的總飽足度，輸出時用相減的就能得到那段的飽足度。

在製作總飽足度陣列時，要計算第 i 項的總飽足度只要把 arr[i - 1] (0 到 i - 1 項的總飽足度) 加上第 i 項的飽足度即可。

完整程式碼

AC (62ms, 332KB)

#include <stdio.h>

int full[100010];

int main()
{
    int n, m, f, t;
    while (scanf(" %d %d", &n, &m) == 2)
    {
        for (int i = 1; i <= n; i++)
        {
            scanf(" %d", &full[i]);
            full[i] += full[i - 1];
        }
        for (int i = 1; i <= m; i++)
        {
            scanf(" %d %d", &f, &t);
            printf("%d\n", full[t] - full[f - 1]);
        }
    }
    return 0;
}