-
Notifications
You must be signed in to change notification settings - Fork 1
/
2016 S4.cpp
139 lines (87 loc) · 4.98 KB
/
2016 S4.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
/*
2016 S4 - Combining Riceballs
Topics: Dynamic Programming
Difficulty: Hard
For this problem, we will create a 2-D array called combinable
combinable[i][j] will tell us whether riceballs from index i to index j can be combined.
Key insight #1:
If riceballs from index i to index j can be combined, does the order they're combined in affect the sum?
Answer: No, regardless of how they're combined, their end result will always be the sum of the riceballs in that interval.
This will allow us to create an array called sum.
sum[i] will tell us the sum of all riceballs from index 0 to index i. We can use sum to calculate the riceball sizes quickly.
largest riceball from i to j = sum[j] - sum[i]
Now comes the tricky part, determining which riceballs can be combined.
To accomplish this, we will iterate through every possible combination size aka 2 -> N-1
For each of these possible combination sizes, we will iterate through every possible starting position
Then for each starting position, we will iterate through all possible front, middle and end block sizes
When checking with the front, middle and end blocks, for combinable[i][j] to be true
The front must be combinable, the middle must be combinable (note that if there's no middle we can exclude it), the end block must be combinable and the front block must equal the end block
Imagine we have the riceballs
2 1 2 21 21 1 3 1
We can view the front block as 2 1 2, which can be combined to equal 5
We can view the middle block as 21 21, which can be combined to equal 42
We can view the end block as 1 3 1, which can also be combined to make 5
Since the front block == end block and they're both combinable, this entire segment is combinable since it can be reduced to
5 42 5
Following the three block rule, this can now be combined into 52
*/
#include <iostream>
#include <vector>
int main(){
int N;
std::cin >> N;
std::vector<int> riceballs (N); //Riceballs
std::vector<int> sum (N); //Sum array, sum[i] = sum from index 0 to index i in the riceballs
//For the first riceball since the remaining sums will make use of the previous sum
std::cin >> riceballs[0];
sum[0] = riceballs[0];
for (int i = 1; i < N; i++){
std::cin >> riceballs[i];
sum[i] = sum[i - 1] + riceballs[i]; //Sum = previous sum + current riceball
}
std::vector<std::vector<bool>> combinable (N, std::vector<bool> (N, false)); //combinable[i][j] tells us whether we can combine riceballs from riceballs[i] to riceballs[j]
//Initialize the base case, all segments of size 1 are possible
for (int i = 0; i < N; i++){
combinable[i][i] = true;
}
//For every possible segment size
for (int range = 1; range < N; range++){
//For every start position
for (int start = 0; start < N - range; start++){
int end = start + range; //end is the END OF THE END BLOCK
int frontBlock = riceballs[start]; //sum of riceballs in front block
int endBlock = riceballs[end]; //sum of riceballs in end block
int frontBlockEnd = start; //frontBlockEnd is the index of the end of the front block
int endBlockBegin = end; //endBlockBegin is the starting index of the end block
//The end of the front block can't go past the beginning of the end block otherwise they'd be eating from one another
while (frontBlockEnd < endBlockBegin){
//if front is combinable, there exists no middle or middle is combinable, end is combinable and front block == end block
if (combinable[start][frontBlockEnd] && (endBlockBegin - 1 < frontBlockEnd + 1 || combinable[frontBlockEnd + 1][endBlockBegin - 1]) && combinable[endBlockBegin][end] && frontBlock == endBlock){
combinable[start][end] = true; //It's possible
break;
}
//If frontblock is smaller than endblock, we should increase add a riceball to it in hopes that it will now equal the end block and possibly allow a merge
if (frontBlock < endBlock){
frontBlockEnd++;
frontBlock += riceballs[frontBlockEnd];
}
//If end block is smaller, we should add a riceball in hopes that it will equal the front block
else{
endBlockBegin--;
endBlock += riceballs[endBlockBegin];
}
}
}
}
int largestRiceball = 0; //Largest possible riceball to be made
//Loop through every range, if it can be combined, determine the sum of riceballs in that range, update max accordingly
for (int i = 0; i < N; i++){
for (int j = 0; j < N; j++){
if (combinable[i][j]){
largestRiceball = std::max(largestRiceball, sum[j] - sum[i] + riceballs[i]); // + riceballs[i] since the substraction of sums actually excludes the initial riceball
}
}
}
std::cout << largestRiceball;
return 0;
}