By ayush29azad, history, 5 weeks ago,

How to solve this problem using Dp ??? I read the editorial and found that it has been solved using combinatorics but I saw others have solved it using Dp approach.

 » 5 weeks ago, # | ← Rev. 2 →   +6 At first,we reverse array B and make array B is non-descending.It is easy to find that if array A and array B combine to form array C, array C is non-descending.Therefore, the answer is equal to the number of non-decending array C whose element is an integer between 1 to n.(The length of array C is 2*n).We assume dp[i][j] means the number of array C whose length is i and maximum value is j.So the answer of this problem is dp[2*m+1][n].The dp function is:dp[i][j]=dp[i-1][1]+dp[i-1][2]+...+dp[i-1][j] So the complexity is O(n*n*m).Since the constraint is too weak.This method is correct.But if the constraint is stronger,you should used some data structure to reduce the time of dp function.It is my code: #include using namespace std; #define int long long const int mod=1e9+7; int dp[22][1002]; signed main() { int h; int t,n, m,a,b,c; cin >> n >> m; for (int i = 1; i <= n; i++) dp[1][i] = 1; for (int i = 2; i <= 2*m+1; i++) { for (int j = 1; j <= n; j++) { for (int k = 1; k <= j; k++) { dp[i][j] += dp[i - 1][k]; } dp[i][j] %= mod; } } cout << dp[2 * m + 1][n] << '\n'; return 0; } 
 » 5 weeks ago, # |   0 You may take a look at this solution Code#define MOD 1000000007 #include using namespace std; void solve() { int n,m;cin>>n>>m; m*=2; vector> dp(m+1,vector(n+1)); for(int i=0;i<=n;++i)dp[1][i]=i; for(int i=0;i<=m;++i)dp[i][1]=1; for(int i=2;i<=m;++i){ for(int j=2;j<=n;++j){ int a=0; for(int k=1;k<=i;++k){ a+=dp[k][j-1]; a%=MOD; } dp[i][j]=(a+1)%MOD; } } cout<