Guest User

Untitled

a guest
Dec 14th, 2018
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.37 KB | None | 0 0
  1. /**__builtin_popcount = int
  2. __builtin_popcountl = long int
  3. __builtin_popcountll = long long**/
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6. #define min(a,b) a > b ? b: a
  7.  
  8. void on( int &mask ,int pos){
  9. mask |= ( 1 << pos) ;
  10. }
  11. void off(int &mask,int pos){
  12. mask = mask & ~( 1 << pos) ;
  13. }
  14. bool check( int mask , int pos ){
  15. return bool( mask & ( 1 << pos) ) ;
  16. }
  17. int dp[ 1<<12 + 5 ] ;
  18.  
  19. int solve( int mask)
  20. {
  21. int &ret = dp[mask];
  22. if( ret != -1 ) return ret;
  23. ret = __builtin_popcount(mask);
  24. for( int pos = 0 ; pos < 12 ; pos ++ )
  25. {
  26. if( pos < 10 && check(mask,pos) && check(mask,pos+1) && !check(mask,pos+2)){
  27. int newmask = mask;
  28. off(newmask,pos) , off( newmask , pos +1 ) , on(newmask,pos+2);
  29. ret = min( ret , solve(newmask));
  30. }
  31. if( pos > 1 && check(mask,pos) && check(mask,pos-1) && !check(mask,pos-2)){
  32. int newmask = mask;
  33. off(newmask,pos) , off( newmask , pos-1 ) , on(newmask,pos-2);
  34. ret = min( ret , solve(newmask));
  35. }
  36. }
  37. return ret;
  38. }
  39. int main()
  40. {
  41. int test , cs = 1 ;
  42. char s[20];
  43. scanf("%d",&test);
  44. while(test--)
  45. {
  46. scanf("%s",&s);
  47. memset(dp,-1,sizeof dp);
  48. int mask = 0 ;
  49. for(int i = 0 ; s[i] ; i++ ) if( s[i] == 'o') on(mask,i);
  50. int ret = solve(mask);
  51. printf("%d\n",ret);
  52. }
  53. }
Add Comment
Please, Sign In to add comment