Mei's Array Merge (Mei's 20240427 Summer Internship Written Exam Questions)

Topic: Merging of Mei's arrays

Mei has been given an array in which she can merge two neighboring elements ai into one element per operation, and the merged element is the sum of the original two elements. Mei wants the minimum value of the final array to be no less than k. She wants to know how many different merging results there are?

Input Description

The first line inputs two positive integers n,k, representing the array size and the maximum value of the array.

On the second line, enter a positive integer ai, representing the array that Mei got.

1<=n,k,ai<=200

Output Description

Output an integer representing how many different results Mei can get. Since the results can be large, output the result of taking a modulo of 10^9+7.

Sample Input

4 4

2 3 4 5

Sample Output

4

clarification

The four arrays that may be obtained are [5,4,5], [9,5], [5,9], and [14].

notes

Memorized Search

First definition:dfs(i,p)Indicates that from the 0th to thei-1number, preceded by the one that did the merge operation. The current number from the firstiThe number of positions begins to consider how many ways there are to merge under this kind of subproblem. Andpdenotes that after doing the merge consideration operation earlier, the firstiWhat is the previous number of a number (in the extreme case the first 0 toi-1The numbers are all merged, and it is also possible that the firsti-1(The individual numbers have not been merged and remain as they were).

So what is the deepest condition of recursion? It'sdfs(n-1,p)Is it? Actually, yes.dfs(n,p)This time indicates that from the first0Element No. 1 to element No.n-1No. elements, a total of n numbers, are done merging, the number of numbers in the subproblem we want to consider is now 0, then the division is 1, but at this point we also have to look at ourpThat is to say, after doing the merge consideration operation earlier, the firstnWhat is the previous number of the number element (which is actually null because the array is just from 0 to n-1), and if this previous number is more thankSmall, indicating that this division is not in line with the requirements, return 0, otherwise it is to meet the requirements, return 1.

Then in the middle layer of the dfs, for thedfs(i,p)IfpThe first is that in the first0Element No. 1 to element No.n-1After considering the merging of the elements, the firstnThe number of elements (which is actually null because the array is from 0 to n-1) that precedes the number thankis small, then it means that if it does not match thea[i]It won't work if you merge (does merging always fulfill the conditions?). Referraldfs(i+1,?)Go ahead and judge it), thendfs(i,p)=dfs(i,p+a[i])And ifp>=k, then it follows that it has no relationship to thea[i]merger or not, it is possible that thedfs(i,p) = dfs(i+1,p+a[i]) + dfs(i+1,p)。

Finally, you can mnemonicize the dfs process and store the return value in the dp array to do a mnemonic search.

(The code is unverified, but the idea is probably along these lines)

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

vector<vector<int>> dp;
vector<int> arr;
int n, k;

int dfs(int i, int p) {
    if (i == n) {
        return p >= k ? 1 : 0;
    }
    if (dp[i][p] != -1) {
        return dp[i][p];
    }
    int cnt = 0;
    if (p >= k) {
        cnt += dfs(i + 1, arr[i]);
        cnt %= MOD;
        cnt += dfs(i + 1, p + arr[i]);
        cnt %= MOD;
    } else {
    	cnt += dfs(i + 1, p + arr[i]);
        cnt %= MOD;
    }
    dp[i][p] = cnt;
    return cnt;
}