Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <iomanip>
- #define MAGIC 2147483647
- #define MINUSINF -2147483647
- #define INF 2147483647
- using namespace std;
- long liczba[501];
- char znak[500];
- long maks[500][500];
- long mini[500][500];
- long tmp[500];
- long getMaxSum(int from, int i, int to); //forward declaration
- long getMaxDiff(int from, int i, int to);
- long getMaxMult(int from, int i, int to);
- long getMinSum(int from, int i, int to);
- long getMinDiff(int from, int i, int to);
- long getMinMult(int from, int i, int to);
- long getMax(int from, int to);
- long getMin(int from, int to);
- int readFile(){
- ifstream in;
- in.open("in");
- int i=0;
- while(!in.eof()){
- in >> liczba[i];
- in >> znak[i];
- i++;
- }
- return i;
- }
- void initArrays(int n){
- for(int i=0; i<n; i++){
- for(int j=0; j<n; j++){
- maks[i][j] = MAGIC;
- mini[i][j] = MAGIC;
- }
- maks[i][i] = liczba[i];
- mini[i][i] = liczba[i];
- }
- }
- int evaluate(int i){
- int result;
- if(znak[i]=='*')
- result = liczba[i]*liczba[i+1];
- if(znak[i]=='+')
- result = liczba[i]+liczba[i+1];
- if(znak[i]=='-')
- result = liczba[i]-liczba[i+1];
- return result;
- }
- long getMaxSum(int from, int i, int to){
- return getMax(from, i) + getMax(i+1, to);
- };
- long getMaxDiff(int from, int i, int to){
- return getMax(from, i) - getMin(i+1, to);
- };
- long getMaxMult(int from, int i, int to){
- long tmp[4];
- tmp[0] = getMax(from, i) * getMax(i+1, to);
- tmp[1] = getMax(from, i) * getMin(i+1, to);
- tmp[2] = getMin(from, i) * getMax(i+1, to);
- tmp[3] = getMin(from, i) * getMin(i+1, to);
- for(int i=1; i<4; i++){
- if(tmp[i]>tmp[0])
- tmp[0] = tmp[i];
- }
- return tmp[0];
- };
- long getMinSum(int from, int i, int to){
- return getMin(from, i) + getMin(i+1, to);
- };
- long getMinDiff(int from, int i, int to){
- return getMin(from, i)-getMax(i+1, to);
- };
- long getMinMult(int from, int i, int to){
- long tmp[4];
- tmp[0] = getMax(from, i) * getMax(i+1, to);
- tmp[1] = getMax(from, i) * getMin(i+1, to);
- tmp[2] = getMin(from, i) * getMax(i+1, to);
- tmp[3] = getMin(from, i) * getMin(i+1, to);
- for(int i=1; i<4; i++){
- if(tmp[i]<tmp[0])
- tmp[0] = tmp[i];
- }
- return tmp[0];
- };
- long getMax(int from, int to){
- if((from-to) == 1){
- return evaluate(from);
- }
- if(from==to)
- return liczba[from];
- long tmp;
- long max = MINUSINF;
- for(int i=0; i<(to-from); i++){
- if(znak[i+from]=='+')
- tmp = getMaxSum(from, from+i, to);
- if(znak[i+from]=='-')
- tmp = getMaxDiff(from, from+i, to);
- if(znak[i+from]=='*')
- tmp = getMaxMult(from, from+i, to);
- if(tmp > max)
- max = tmp;
- }
- return max;
- }
- long getMin(int from, int to){
- if((from-to) == 1){
- return evaluate(from);
- }
- if(from==to)
- return liczba[from];
- long tmp;
- long min = INF;
- for(int i=0; i<(to-from); i++){
- if(znak[i+from]=='+')
- tmp = getMinSum(from, from+i, to);
- if(znak[i+from]=='-')
- tmp = getMinDiff(from, from+i, to);
- if(znak[i+from]=='*')
- tmp = getMinMult(from, from+i, to);
- if(tmp < min)
- min = tmp;
- }
- return min;
- }
- int main(){
- int n = readFile();
- initArrays(n);
- n--;
- cout << n<<endl;
- cout << getMax(0,n)<<endl;
- cout << getMin(0,n)<<endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement