Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int arrangeBuildings(int plot, int lastPlotUsedFor, int &n, vector<vector<int> > &memo){
- if(plot >= n){
- return 1;
- }
- if(lastPlotUsedFor != -1 && memo[plot][lastPlotUsedFor] != 0){
- return memo[plot][lastPlotUsedFor];
- }
- //levels - plot
- //options - either make a building in the plot or not(leave as is)
- /*
- lastPlotUsedFor = -1 [we are exploring options for 0th plot]
- = 0 [last plot was left as is]
- = 1 [last plot was used for a building]
- */
- // At each level, explore all the valid options
- //make building
- //This call can only be made if we are at the first plot (which have no previous), or the previous plot had a space
- // We do this as if the previous plot/level was used for a building, making a building at the current level would make buildings consecutive, breaking the constraint.
- int built = 0, notBuilt = 0;
- if(lastPlotUsedFor == -1 || lastPlotUsedFor == 0){
- built = arrangeBuildings(plot + 1, 1, n, memo);
- }
- //not make building
- notBuilt = arrangeBuildings(plot + 1, 0, n, memo);
- if(lastPlotUsedFor != -1){
- memo[plot][lastPlotUsedFor] = built + notBuilt;
- }
- return built + notBuilt;
- }
- long long arrangeBuildingsDP(int &n){
- /*
- Storage & Meaning - dp[i][0] = ways to arrange buildings in i plots where last plot is to be left (should be empty)
- dp[i][1] = ways to arrange buildings in i plots where last plot is used to make buildings
- */
- vector<vector<int> > dp(n + 1, vector<int>(2, 0));
- /*
- Direction - Smallest Problem at:
- dp[1][0] = ways to arrange buildings if only 1 plot is there and last plot should be empty = 1 way (leave it empty)
- dp[1][1] = ways to arrange buildings if only 1 plot is there and last plot should have a building = 1 way (make one)
- Largest problem at dp[n][0] & dp[n][1]
- As our problem asks how many ways are there to arrange buildings if there were n plots
- dp[n][0] = ways to arrange if n plots available, last plot should be empty
- dp[n][1] = ways to arrange if n plots available, last plot should have a building
- Either of them have n plots, totalling/summation them would give the answer to the question
- */
- dp[1][0] = dp[1][1] = 1;
- /*
- Travel & Solve - Travel in the direction from small problem to large problem with transitions as captured in tree/memo/recursive code
- */
- for(int i = 2; i <= n; i++){
- dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
- dp[i][1] = dp[i - 1][0];
- }
- // As there are 2 rows of plot (each would return dp[n] ways)
- // So the total ways would be dp[n] * dp[n];
- return pow((long long) (dp[n][0] + dp[n][1]), 2);
- }
- int main() {
- // your code goes here
- int n;
- cin >> n;
- vector<vector<int> > memo(n + 1, vector<int>(2, 0));
- cout << pow((long long) arrangeBuildings(0, -1, n, memo), 2) << '\n';
- cout << arrangeBuildingsDP(n) << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
