Write some DP

Flowers   【noip2012】 Popularization group

Title Description

Xiaoming's florist is newly opened , To attract customers , He wants to put a row of flowers in front of the flower shop , common  m  basin . By investigating customer preferences , Xiao Ming listed the customers' favorite  n  grow flowers , from  1  To  n  label . To show more flowers at the door , Rule No  i  You can't plant more than  ai  basin , When arranging flowers, put the same kind of flowers together , And different kinds of flowers need to be arranged in order from small to large .

Trial programming calculation , How many different flower arrangements are there .

Input format

The first line contains two positive integers  n  and  m, Separated by a space .

The second line has  n  It's an integer , Every two integers are separated by a space , Sequential representation  a1,⋯,an​.

Output format

An integer , Indicates how many options there are . Be careful ： Because the number of schemes may be many , Please output the number of scheme pairs  10^6+7  Results of die taking .

I/o sample

Input #1 Copy

2 4
3 2

Output #1 Copy

2

explain / Tips

【 Data range 】

about  20\%20%  data , Yes  0<n \le 8,0<m \le 8,0 \le a_i \le 80<n≤8,0<m≤8,0≤ai​≤8.

about  50\%50%  data , Yes  0<n \le 20,0<m \le 20,0 \le a_i \le 200<n≤20,0<m≤20,0≤ai​≤20.

about  100\%100%  data , Yes  0<n \le 100,0<m \le 100,0 \le a_i \le 1000<n≤100,0<m≤100,0≤ai​≤100.

NOIP 2012 Popularization group Third question

1. Search for

#include<bits/stdc++.h>
using namespace std;
const int maxn=105, mod = 1000007;
int n, m, a[maxn];
int dfs(int x,int k)
{
    if(k > m) return 0;
    if(k == m) return 1;
    if(x == n+1) return 0;
    int ans = 0;
    for(int i=0; i<=a[x]; i++) ans = (ans + dfs(x+1, k+i))%mod;
    return ans;
}
int main()
{
    cin>>n>>m;
    for(int i=1; i<=n; i++) cin>>a[i];
    cout<<dfs(1,0)<<endl;
    return 0;
}

 2. Memory search

#include<bits/stdc++.h>
using namespace std;
const int maxn=105, mod = 1000007;
int n, m, a[maxn], rmb[maxn][maxn];
int dfs(int x,int k)
{
    if(k > m) return 0;
    if(k == m) return 1;
    if(x == n+1) return 0;
    if(rmb[x][k]) return rmb[x][k]; // Search and return 
    int ans = 0;
    for(int i=0; i<=a[x]; i++) ans = (ans + dfs(x+1, k+i))%mod;
    rmb[x][k] = ans; // Record the results of the current state 
    return ans;
}
int main()
{
    cin>>n>>m;
    for(int i=1; i<=n; i++) cin>>a[i];
    cout<<dfs(1,0)<<endl;
    return 0;
}

3. Two dimensional dynamic programming

#include<bits/stdc++.h>
using namespace std;
const int maxn=105, mod = 1000007;
int n, m, a[maxn], f[maxn][maxn];
int main()
{
    cin>>n>>m;
    for(int i=1; i<=n; i++) cin>>a[i];
    f[0][0] = 1;
    for(int i=1; i<=n; i++)
       for(int j=0; j<=m; j++)
           for(int k=0; k<=min(j, a[i]); k++)
              f[i][j] = (f[i][j] + f[i-1][j-k])%mod;
    cout<<f[n][m]<<endl;
    return 0;
}

4. One dimensional dynamic programming

#include<bits/stdc++.h>
using namespace std;
const int maxn=105, mod = 1000007;
int n, m, a[maxn], f[maxn];
int main()
{
    cin>>n>>m;
    for(int i=1; i<=n; i++) cin>>a[i];
    f[0] = 1;
    for(int i=1; i<=n; i++)
        for(int j=m; j>=0; j--) // Be careful , yes 01 knapsack 
            for(int k=1; k<=min(a[i], j); k++)
              f[j] = (f[j] + f[j-k])%mod;
    cout<<f[m]<<endl;
    return 0;
}