[text] flip array

Viewer

copydownloadembedprintName: flip array
  1. pair<int,int> arr[101][(int)pow(10,4)+1][2];
  2. pair<int,int> flip(vector<int> a)
  3. {
  4.     /*if(len==0 && sum<0) return {INT_MAX,INT_MAX};
  5.     if(len==0) return {sum,0};
  6.     pair<int,int> op1 = flip(a,len-1,sum+a[len-1]);
  7.     pair<int,int> op2 = {INT_MAX,INT_MAX};
  8.     if(flip(a,len-1,sum-a[len-1])!=make_pair(INT_MAX,INT_MAX))
  9.     {
  10.         op2.first = flip(a,len-1,sum-a[len-1]).first;
  11.         op2.second = 1 + flip(a,len-1,sum-a[len-1]).second;
  12.     }
  13.     return min(op1,op2);*/
  14.     int sum =  accumulate(a.begin(),a.end(),0);
  15.     int len = a.size();
  16.     for(int i=0;i<=len;i++)
  17.     {
  18.         for(int j=0;j<=sum;j++)
  19.         {
  20.             for(int k=0;k<=1;k++)
  21.             {
  22.                 if(i==0)
  23.                 {
  24.                     if(k==0 && j>0) arr[i][j][k] = {INT_MAX,INT_MAX};
  25.                     else arr[i][j][k] = {j,0};
  26.                 }
  27.                 else
  28.                 {
  29.                     pair<int,int> op1 = {INT_MAX,INT_MAX};
  30.                     pair<int,int> op2 = {INT_MAX,INT_MAX};
  31.                     if(k==0)
  32.                     {
  33.                         if(-j + a[i-1] < 0) op1 = arr[i-1][j-a[i-1]][0];
  34.                         else op1 = arr[i-1][a[i-1]-j][1];
  35.                         if(arr[i-1][j+a[i-1]][0] != make_pair(INT_MAX,INT_MAX))
  36.                         {
  37.                             op2.first = arr[i-1][j+a[i-1]][0].first;
  38.                             op2.second = 1 + arr[i-1][j+a[i-1]][0].second;
  39.                         }
  40.                         arr[i][j][k] = min(op1,op2);
  41.                     }
  42.                     else if(k==1)
  43.                     {
  44.                         op1 = arr[i-1][j+a[i-1]][1];
  45.                         if(j-a[i-1]>=0)
  46.                         {
  47.                             if(arr[i-1][j-a[i-1]][1] !=make_pair(INT_MAX,INT_MAX))
  48.                             {
  49.                                 op2.first = arr[i-1][j-a[i-1]][1].first;
  50.                                 op2.second = 1 + arr[i-1][j-a[i-1]][1].second;
  51.                             }
  52.                         }
  53.                         else
  54.                         {
  55.                             if(arr[i-1][a[i-1]-j][0] !=make_pair(INT_MAX,INT_MAX))
  56.                             {
  57.                                 op2.first = arr[i-1][a[i-1]-j][0].first;
  58.                                 op2.second = 1 + arr[i-1][a[i-1]-j][0].second;
  59.                             }
  60.                         }
  61.                         arr[i][j][k] = min(op1,op2);
  62.                     }
  63.                 }
  64.             }
  65.         }
  66.     }
  67.     return arr[len][0][0];
  68. }
  69. int Solution::solve(const vector<int> &a) {
  70.     return flip(a).second;
  71. }

Editor

You can edit this paste and save as new:


File Description
  • flip array
  • Paste Code
  • 25 Aug-2019
  • 2.64 Kb
You can Share it: