- pair<int,int> arr[101][(int)pow(10,4)+1][2];
- pair<int,int> flip(vector<int> a)
- {
- /*if(len==0 && sum<0) return {INT_MAX,INT_MAX};
- if(len==0) return {sum,0};
- pair<int,int> op1 = flip(a,len-1,sum+a[len-1]);
- pair<int,int> op2 = {INT_MAX,INT_MAX};
- if(flip(a,len-1,sum-a[len-1])!=make_pair(INT_MAX,INT_MAX))
- {
- op2.first = flip(a,len-1,sum-a[len-1]).first;
- op2.second = 1 + flip(a,len-1,sum-a[len-1]).second;
- }
- return min(op1,op2);*/
- int sum = accumulate(a.begin(),a.end(),0);
- int len = a.size();
- for(int i=0;i<=len;i++)
- {
- for(int j=0;j<=sum;j++)
- {
- for(int k=0;k<=1;k++)
- {
- if(i==0)
- {
- if(k==0 && j>0) arr[i][j][k] = {INT_MAX,INT_MAX};
- else arr[i][j][k] = {j,0};
- }
- else
- {
- pair<int,int> op1 = {INT_MAX,INT_MAX};
- pair<int,int> op2 = {INT_MAX,INT_MAX};
- if(k==0)
- {
- if(-j + a[i-1] < 0) op1 = arr[i-1][j-a[i-1]][0];
- else op1 = arr[i-1][a[i-1]-j][1];
- if(arr[i-1][j+a[i-1]][0] != make_pair(INT_MAX,INT_MAX))
- {
- op2.first = arr[i-1][j+a[i-1]][0].first;
- op2.second = 1 + arr[i-1][j+a[i-1]][0].second;
- }
- arr[i][j][k] = min(op1,op2);
- }
- else if(k==1)
- {
- op1 = arr[i-1][j+a[i-1]][1];
- if(j-a[i-1]>=0)
- {
- if(arr[i-1][j-a[i-1]][1] !=make_pair(INT_MAX,INT_MAX))
- {
- op2.first = arr[i-1][j-a[i-1]][1].first;
- op2.second = 1 + arr[i-1][j-a[i-1]][1].second;
- }
- }
- else
- {
- if(arr[i-1][a[i-1]-j][0] !=make_pair(INT_MAX,INT_MAX))
- {
- op2.first = arr[i-1][a[i-1]-j][0].first;
- op2.second = 1 + arr[i-1][a[i-1]-j][0].second;
- }
- }
- arr[i][j][k] = min(op1,op2);
- }
- }
- }
- }
- }
- return arr[len][0][0];
- }
- int Solution::solve(const vector<int> &a) {
- return flip(a).second;
- }
[text] flip array
Viewer
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:
Latest Code Pastes