All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Chef loves brackets. So much so, that rather than just use plain brackets like (), {}, or [], he has invented his own notation that allows him to use many more types of brackets.
Each type of bracket is designated by an integer. A negative integer -x represents an opening bracket of type x; while a positive integer x represents a closing bracket of type x. Any sequence of such integers is then called a bracket-pair sequence.
A balanced bracket-pair sequence can be defined recursively as follows:
- The empty sequence is a balanced bracket-pair sequence.
- If S is a balanced bracket-pair sequence, then -x S x is a balanced bracket-pair sequence for any positive integer x.
- If S and T are balanced bracket-pair sequences, then S T is a balanced bracket-pair sequence.
For example, "-1 -2 2 -3 -4 4 3 1" is a balanced bracket-pair sequence, but "-1 -2 1 2" is not.
Chef has a bracket-pair sequence (which may or may not be balanced) consisting of N integers. There are 2N ways to form a subsequence of his sequence. He wants to know how many of these subsequences are balanced.
Help him to calculate this number, modulo 109+7.
Input
The first line contains a single integer N denoting the number of brackets in his sequence.
The second line contains N space-separated integers A1, A2, ..., AN denoting the types of brackets. A negative number means an opening bracket; a positive number means a closing bracket.
Output
In a single line print the required answer.
Constraints
- 1 ≤ N ≤ 100
- -109 ≤ Ai ≤ 109
- Ai ≠ 0
- It is not guaranteed that each opening bracket has a closing bracket of same type and vice-versa.
Subtasks
- Subtask N ≤ 10 Points: 10
- Subtask N ≤ 20 Points: 15
- Subtask N ≤ 100 Points: 75
Example
Input: 11 -1 -2 9 2 -3 -4 3 4 8 8 1 Output: 12
A very good and interesting DP question that requires an O(n^3) approach.
first read this explanation
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
#define mod 1000000007
long long int dp[110][110];
int arr[110];
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
for(int len=0;len<n;len++)
{
for(int i=0;i<n;i++)
{
int j=(len+i);
if(j>n-1 || i==j)
continue;
dp[i][j]=dp[i][j-1];
for(int k=i;k<j;k++)
{
if(arr[j]>0 && arr[j]==-1*arr[k])
{
if(k==i)
{
dp[i][j]=(1+dp[i][j]+dp[k+1][j-1])%mod;
}
else
dp[i][j]=(dp[i][j]+((1+dp[i][k-1])*(1+dp[k+1][j-1])%mod))%mod;
}
}
}
}
cout<<(dp[0][n-1]+1)%mod<<endl;
return 0;
}
Ok I'll try to explain it in a really simple way.The first step of solving dynamic programming problems is that you start thinking in a recursive manner. Hows that done you may ask !.
- Assume that by time travel(5D->blackhole->3D) you have a solution already. In this case lets say you have an array of numbers and you already know the solution for brackets problem for this array. Lets call this array as
arr[0,N-1] Or arr[i,j] if you like to generalize- Ask your self- What the chuck would happen if I add one cute little number to the end of this array. No big deal ..just a number. So here is the thing.. array and a new number added to the end of it..(new number = 4).
- Lets say answer for this array was
S[0,N-1]- Now try to understand what can happen when you add 4 to the end of this array. This '4' will form a bracket with any '-4' present in the array right?. Lets put a -4 somewhere.
Now this newly added 4 will form a bracket with this '-4'. So total brackets in this new array (arr[0,N]) is solutions for old one + 1.S[0,N-1] + 1Now thats not the only new bracket that got created. If you see carefully all the brackets in the region [k+1,N-1] can now be put inside the {-4,4} bracket. Like this->-4 {} 4So our new bracket count becomes-S[0,N-1] + 1 + S[k+1, N-1]Correct..Now what else..All the brackets in the region S[0,K-1] can now be coupled with all of these new brackets to create new brackets. Like-{-A A}{-4 4} OR {-A A}{-4 {} 4} . . .So our new bracket count becomes-S[0,N-1] + 1 + S[k+1, N-1] + (1+S[k+1,N-1])*S[0,k-1]Because all the brackets in region (0,k-1) can go with the newly created (1+S[k+1,N-1]) brackets. Thats why we used multiply. So total count now becomes(What a mess by just adding one number eh? :D)S[0,N-1] + (1 + S[k+1,N-1]) * (1 + S[0,K-1])Thats it..pHew..but wait..what will happen if we have multiple '-4's ????. Well, we will repeat this process for all those -4's.
- Now lets generalize this thing and write a formula-
S[i,j] = S[i,j-1] + (FOR all k such that arr[k] == -arr[j]) (1+S[i,k-1])*(S[k+1,j-1]+1)Now you have successfully created a recurrence relation. Second step is how to write dynammic programming code for this thing. If you see that to calculate value for a range [i,j] you require values of ranges [i,k-1] and [k+1,j-1] which are definitely smaller ranges when compared to [i,j]. So while writing dp code for this what you have to do is find values of all the small ranges before proceeding to the bigger ranges. Which in lay man terms means->
- Find values for ranges [0,0], [1,1], [2,2], [3,3] ....[i,i]...[N-1,N-1]
- Find values for ranges [0,1], [1,2], [2,3], [3,4], ...[i,i+1]....[N-2,N-1]
- Find values for ranges [0,k], [1,1+k], [2,2+k]...[i, i+k] ....[N-k-1, N-1]
- do it for [0,N-1] and we are done.
Now let us see the coding part;We run a loop for a valid length of a bracket sequence and that is from 0 to n;Now for all lengths we fix the starting position of the bracket sequence from i=0 to <nnow we calculate the end point as j=i+lenevidently dp[i][j]=dp[i][j-1]now we run loop from k=i to<jand if arr[j]>0 && arr[k]=-1*arr[j] we use the recursive relation to find the number of bracket sequences;Now it is important to note that if i==kwe just add 1+dp[k+1][j-1] to dp[i][j]the output is dp[0][n-1]+1 [note 1 is for the empty subset]
No comments:
Post a Comment