第7关：204_蓄水池

任务描述

工地有一个n升蓄水池，现在需要将它灌满水（不能溢出），当第i次灌水的时候，可以灌入1至num[i-1]升水。

问有多少种灌满水的方法？答案可能很大，答案对1e9+7取模。

• 1 <= n <= 10^6 • 1 <= num[i] <=10^6

样例

给出n=2，num=[2,2]，返回2。

解释:

可以倒入2次1升的水，也可以在第1次倒入2升的水。

给出n=3，num=[3,2,1]，返回4

解释:

方案一：第1次倒入3升的水。 方案二：第1次倒入1升的水，第2次倒入2升的水。 方案三：第1次倒入2升的水，第2次倒入1升的水。 方案四：第1次倒入1升的水，第2次倒入1升的水，第3次倒入1升的水。

测试说明

平台会对你编写的代码进行测试：

测试输入： 3 3 2 1

预期输出： 4

f[i][j]表示第i次倒入后水深为j。

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <cmath>
#include <algorithm>
#define P 1000000007
using namespace std;

void Solve() {
    int n;
    cin >> n;
    int num[n+5] = {0},f[n+5][n+5] = {0};
    memset(f,0,sizeof(f));
    for(int i = 0;i < n;i++) {
        cin >> num[i];
    }
    
    for(int i = 1;i <= num[0];i++) {
        f[1][i] = 1;
    }
    //第一次倒入水，都只有一种
    
    for(int i = 2;i <= n;i++) {
        for(int j = i;j <= n;j++) {
            for(int k = 1;k <= num[i-1];k++) {
                if(j-k <= 0) {
                    break;
                }
                f[i][j] += f[i-1][j-k];
                //第i次水深为j的方法数是第i-1次水深为j-k的方法的总和
                //j-k表示第i-1次的水深再加k就等于第i次水深j
                //k的范围是第i次所能再加的水
                //题述：当第i次灌水的时候，可以灌入1至num[i-1]升水。
                f[i][j] %= P;
            }
        }
    }
    
   /* for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= n;j++) {
            cout << f[i][j] << " ";
        }
        cout << endl;
    }*/
    
    int cnt = 0;
    for(int i = 1;i <= n;i++) {
        cnt += f[i][n];//所有水深为n的加起来为总方法数
        cnt %= P;//不要忘了对1e9+7取模
    }
    cnt %= P;
    
    cout << cnt << endl;
}

int main()
{
    Solve();
    return 0;
}