Advertisement
Guest User

Untitled

a guest
Nov 24th, 2014
171
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.95 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <iomanip>
  4.  
  5. #define MAGIC 2147483647
  6. #define MINUSINF -2147483647
  7. #define INF 2147483647
  8. using namespace std;
  9.  
  10. long liczba[501];
  11. char znak[500];
  12. long maks[500][500];
  13. long mini[500][500];
  14.  
  15. long tmp[500];
  16.  
  17. long getMaxSum(int from, int i, int to); //forward declaration
  18. long getMaxDiff(int from, int i, int to);
  19. long getMaxMult(int from, int i, int to);
  20. long getMinSum(int from, int i, int to);
  21. long getMinDiff(int from, int i, int to);
  22. long getMinMult(int from, int i, int to);
  23. long getMax(int from, int to);
  24. long getMin(int from, int to);
  25.  
  26. void printMaxMin(int n){
  27.  
  28.     cout << "max";
  29.     for(int i=0; i<n; i++){
  30.         cout << "\t" << setfill('0') << setw(11) << i;
  31.     }
  32.     cout << endl;
  33.     for(int i=0; i<n; i++){
  34.         cout << i << "|";
  35.         for(int j=0; j<n; j++){
  36.             cout << "\t" << setfill('0') << setw(11) << maks[i][j];
  37.         }
  38.         cout << endl;
  39.  
  40.     }
  41.  
  42.     cout << "min";
  43.     for(int i=0; i<n; i++){
  44.         cout << "\t" << setfill('0') << setw(11) << i;
  45.     }
  46.     cout << endl;
  47.     for(int i=0; i<n; i++){
  48.         cout << i << "|";
  49.         for(int j=0; j<n; j++){
  50.             cout << "\t" << setfill('0') << setw(11) << mini[i][j];
  51.         }
  52.         cout << endl;
  53.  
  54.     }
  55. }
  56.  
  57.  
  58. int readFile(){
  59.     ifstream in;
  60.     in.open("in");
  61.     int i=0;
  62.     while(!in.eof()){
  63.         in >> liczba[i];
  64.         in >> znak[i];
  65.         i++;
  66.     }
  67.     return i;
  68. }
  69.  
  70. void initArrays(int n){
  71.     for(int i=0; i<n; i++){
  72.         for(int j=0; j<n; j++){
  73.             maks[i][j] = MAGIC;
  74.             mini[i][j] = MAGIC;
  75.         }
  76.         maks[i][i] = liczba[i];
  77.         mini[i][i] = liczba[i];
  78.     }
  79. }
  80.  
  81. int evaluate(int i){
  82.     if(maks[i][i+1] != MAGIC)
  83.         return maks[i][i+1];
  84.  
  85.     int result;
  86.     if(znak[i]=='*')
  87.         result = liczba[i]*liczba[i+1];
  88.     if(znak[i]=='+')
  89.         result = liczba[i]+liczba[i+1];
  90.     if(znak[i]=='-')
  91.         result = liczba[i]-liczba[i+1];
  92.  
  93.     maks[i][i+1] = result;
  94.     mini[i][i+1] = result;
  95.     return result;
  96. }
  97.  
  98. long getMaxSum(int from, int i, int to){
  99.     return getMax(from, i) + getMax(i+1, to);
  100. };
  101. long getMaxDiff(int from, int i, int to){
  102.     return getMax(from, i) - getMin(i+1, to);
  103. };
  104.  
  105. long getMaxMult(int from, int i, int to){
  106.     long tmp[4];
  107.     tmp[0] = getMax(from, i) * getMax(i+1, to);
  108.     tmp[1] = getMax(from, i) * getMin(i+1, to);
  109.     tmp[2] = getMin(from, i) * getMax(i+1, to);
  110.     tmp[3] = getMin(from, i) * getMin(i+1, to);
  111.  
  112.     for(int i=1; i<4; i++){
  113.         if(tmp[i]>tmp[0])
  114.             tmp[0] = tmp[i];
  115.     }
  116.     return tmp[0];
  117. };
  118.  
  119. long getMinSum(int from, int i, int to){
  120.     return getMin(from, i) + getMin(i+1, to);
  121. };
  122. long getMinDiff(int from, int i, int to){
  123.     return getMin(from, i)-getMax(i+1, to);
  124. };
  125. long getMinMult(int from, int i, int to){
  126.     long tmp[4];
  127.     tmp[0] = getMax(from, i) * getMax(i+1, to);
  128.     tmp[1] = getMax(from, i) * getMin(i+1, to);
  129.     tmp[2] = getMin(from, i) * getMax(i+1, to);
  130.     tmp[3] = getMin(from, i) * getMin(i+1, to);
  131.  
  132.     for(int i=1; i<4; i++){
  133.         if(tmp[i]<tmp[0])
  134.             tmp[0] = tmp[i];
  135.     }
  136.     return tmp[0];
  137. };
  138.  
  139. long getMax(int from, int to){
  140.     if(maks[from][to] != MAGIC)
  141.         return maks[from][to];
  142.  
  143.     if((from-to) == 1){
  144.         return evaluate(from);
  145.     }
  146.     long tmp;
  147.     long max = MINUSINF;
  148.     for(int i=0; i<(to-from); i++){
  149.         if(znak[i+from]=='+')
  150.             tmp = getMaxSum(from, from+i, to);
  151.         if(znak[i+from]=='-')
  152.             tmp = getMaxDiff(from, from+i, to);
  153.         if(znak[i+from]=='*')
  154.             tmp = getMaxMult(from, from+i, to);
  155.         if(tmp > max)
  156.             max = tmp;
  157.     }
  158.  
  159.     maks[from][to] = max;
  160.     return max;
  161.  
  162. }
  163.  
  164. long getMin(int from, int to){
  165.     if(mini[from][to] != MAGIC)
  166.         return mini[from][to];
  167.  
  168.     if((from-to) == 1){
  169.         return evaluate(from);
  170.     }
  171.  
  172.     long tmp;
  173.     long min = INF;
  174.     for(int i=0; i<(to-from); i++){
  175.         if(znak[i+from]=='+')
  176.             tmp = getMinSum(from, from+i, to);
  177.         if(znak[i+from]=='-')
  178.             tmp = getMinDiff(from, from+i, to);
  179.         if(znak[i+from]=='*')
  180.             tmp = getMinMult(from, from+i, to);
  181.         if(tmp < min)
  182.             min = tmp;
  183.     }
  184.     mini[from][to] = min;
  185.     return min;
  186. }
  187.  
  188. int main(){
  189.     int n = readFile();
  190.     initArrays(n);
  191.     n--;
  192.     cout << n<<endl;
  193.     cout << getMax(0,n)<<endl;
  194.     cout << getMin(0,n)<<endl;
  195.     //printMaxMin(n+1);
  196.     return 0;
  197. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement