Input Format : Line 1: An Integer N, denoting the number of binary strings. Next N lines: strings of equal length
Output Format : Return the minimum number of touches. (Integer)
Sample Input :
2 111010 100100
Sample Output : 2
int cal(int pos, int mask, vector<string>&v, int **dp){
if(dp[pos][mask] != INT_MAX){
return dp[pos][mask];
}
if(mask&(mask-1)==0){
return 0;
}
if(pos<0){
return 10000;
}
int mask1=0;
int mask2=0;
int count=0;
for(int i=0;i<v.size();i++){
if(mask&(1<<i)==1){
count++;
if(v[i][pos]=='0'){
mask1 |= 1<<i;
}
else{
mask2 |= 1<<i;
}
}
}
int ans = min(count + cal(pos-1,mask1,v,dp) + cal(pos-1,mask2,v,dp) , cal(pos-1,mask,v,dp));
dp[pos][mask] = ans;
return ans;
}
int minimumTouchesRequired(int n, vector<string> v) {
cout<<"here";
int** dp = new int*[v[0].size()];
for(int i=0;i<v[0].size();i++){
dp[i] = new int[(1<<(n+1))];
for(int j=0;j<(1<<(n+1));j++){
dp[i][j] = INT_MAX;
}
}
return cal(v[0].size()-1,(1<<n)-1,v,dp);
}
Aucun commentaire:
Enregistrer un commentaire