SPOJ 9894 Tichu ( 状态压缩 )

举报
Linux猿 发表于 2021/08/04 23:01:49 2021/08/04
【摘要】 题目链接~~> 做题感悟:这题第一感觉就是麻烦,不但输出最小的次数,而且还要输出路径。。。。 解题思路:状态压缩                 这题和 13 年的杭州网络赛的一题差不多,状态压缩 + 01 背包的思想 ,主要是预处理出所有合法的状态就好办了,然后类似 01 背包的方...

题目链接~~>

做题感悟:这题第一感觉就是麻烦,不但输出最小的次数,而且还要输出路径。。。。

解题思路:状态压缩

                这题和 13 年的杭州网络赛的一题差不多,状态压缩 + 01 背包的思想 ,主要是预处理出所有合法的状态就好办了,然后类似 01 背包的方法去更新就可以了。

代码:


  
  1. #include<iostream>
  2. #include<sstream>
  3. #include<map>
  4. #include<cmath>
  5. #include<fstream>
  6. #include<queue>
  7. #include<vector>
  8. #include<sstream>
  9. #include<cstring>
  10. #include<cstdio>
  11. #include<stack>
  12. #include<bitset>
  13. #include<ctime>
  14. #include<string>
  15. #include<cctype>
  16. #include<iomanip>
  17. #include<algorithm>
  18. using namespace std ;
  19. #define INT long long int
  20. #define L(x) (x * 2)
  21. #define R(x) (x * 2 + 1)
  22. const int INF = 0x3f3f3f3f ;
  23. const double esp = 0.00000000001 ;
  24. const double PI = acos(-1.0) ;
  25. const int mod = 1000000007 ;
  26. const int MY = (1<<5) + 5 ;
  27. const int MX = (1<<13) + 5 ;
  28. const int S = 20 ;
  29. int num ;
  30. int A[MX] ,B[MX] ;
  31. char s[20][5] ;
  32. int key[MX] ,dp[MX] ;
  33. vector<int>ans ;
  34. struct node
  35. {
  36. int id ,c ;
  37. }T[50] ;
  38. bool cmp(node a ,node b)
  39. {
  40. return a.c < b.c ;
  41. }
  42. void work(int i ,char ch) // 转化
  43. {
  44. T[i].id = i ; // 原始坐标 用于输出
  45. if(ch >= '2' && ch <= '9') T[i].c = ch - '2' ; // 转化为数值
  46. else if(ch == 'T') T[i].c = 8 ;
  47. else if(ch == 'J') T[i].c = 9 ;
  48. else if(ch == 'Q') T[i].c = 10 ;
  49. else if(ch == 'K') T[i].c = 11 ;
  50. else if(ch == 'A') T[i].c = 12 ;
  51. }
  52. void dfs(int i ,int pre ,int cnt ,int K)
  53. {
  54. if(cnt >= 5) // 符合要求
  55. {
  56. if(key[num-1] != K)
  57. key[num++] = K ;
  58. }
  59. if(i >= 13) return ;
  60. if(T[i].c == T[pre].c + 1) // 选入第 i 个
  61. dfs(i+1 ,i ,cnt+1 ,K|(1<<i)) ;
  62. dfs(i+1 ,pre ,cnt ,K) ; // 不选
  63. }
  64. void solve() // 预处理状态
  65. {
  66. sort(T ,T+13 ,cmp) ; // 数值从小到大
  67. // 单张
  68. for(int i = 0 ;i < 13 ; ++i)
  69. key[num++] = 1<<i ;
  70. //相同数字两张 三张 四张
  71. int t1 = 0 ,t2 = 0 ;
  72. for(int i = 0 ;i < 13 ; ++i)
  73. for(int j = i+1 ;j < 13 ; ++j) // 两张相同
  74. {
  75. if(T[j].c == T[i].c)
  76. {
  77. key[num++] = (1<<i) + (1<<j) ;
  78. //cout<<i<<" "<<j<<endl ;
  79. A[t1++] = key[num-1] ;
  80. }
  81. for(int k = j+1 ;k < 13 ; ++k) // 三张相同
  82. {
  83. if(T[i].c == T[j].c && T[i].c == T[k].c)
  84. {
  85. key[num++] = (1<<i) + (1<<j) + (1<<k) ;
  86. B[t2++] = key[num-1] ;
  87. //cout<<i<<" "<<j<<" "<<k<<" "<<endl ;
  88. }
  89. for(int d = k+1 ;d < 13 ; ++d) // 四张相同
  90. if(T[i].c == T[j].c && T[i].c == T[k].c && T[i].c == T[d].c)
  91. key[num++] = (1<<i) + (1<<j) + (1<<k) + (1<<d) ;
  92. }
  93. }
  94. for(int i = 0 ;i < t2 ; ++i) // 三张 + 两张
  95. for(int j = 0 ;j < t1 ; ++j)
  96. if(!(B[i]&A[j]))
  97. key[num++] = (B[i]|A[j]) ;
  98. // 连续 5 个数或者 5 个以上
  99. for(int i = 0 ;i < 9 ; ++i)
  100. dfs(i+1 ,i ,1 ,1<<i) ;
  101. }
  102. void DP() //
  103. {
  104. memset(dp ,-1 ,sizeof(dp)) ;
  105. dp[0] = 0 ;
  106. for(int S = 0 ;S < (1<<13) ; ++S)
  107. if(dp[S] != -1)
  108. {
  109. for(int i = 0 ;i < num ; ++i)
  110. if(!(S&key[i]))
  111. {
  112. if(dp[S|key[i]] == -1)
  113. dp[S|key[i]] = dp[S] + 1 ;
  114. else dp[S|key[i]] = min(dp[S|key[i]] ,dp[S] + 1) ;
  115. }
  116. }
  117. }
  118. void print(int S) // 找路径
  119. {
  120. for(int i = 0 ;i < num ; ++i)
  121. if((S&key[i]) && dp[S] == dp[S^key[i]] + 1)
  122. {
  123. ans.push_back(i) ;
  124. print((S^key[i])&((1<<13)-1)) ;
  125. break ;
  126. }
  127. }
  128. int main()
  129. {
  130. //freopen("input.txt" ,"r" ,stdin) ;
  131. int Tx ;
  132. scanf("%d" ,&Tx) ;
  133. while(Tx--)
  134. {
  135. num = 0 ; // 存合法状态
  136. ans.clear() ;
  137. for(int i = 0 ;i < 13 ; ++i)
  138. {
  139. scanf("%s" ,s[i]) ;
  140. work(i ,s[i][0]) ;
  141. }
  142. solve() ;
  143. DP() ;
  144. print((1<<13)-1) ;
  145. cout<<dp[(1<<13)-1]<<endl ;
  146. vector<int>Tp ;
  147. for(int i = 0 ;i < (int)ans.size() ; ++i)
  148. {
  149. Tp.clear() ;
  150. int temp = key[ans[i]] ;
  151. for(int i = 0 ;i < 13 ; ++i)
  152. if(temp&(1<<i))
  153. Tp.push_back(i) ;
  154. if(Tp.size() == 5 && Tp[0] == Tp[1]) // 防止 1 1 2 2 2 的之中情况
  155. {
  156. if(Tp[1] != Tp[2])
  157. {
  158. cout<<s[T[Tp[4]].id] ;
  159. for(int i = Tp.size()-2 ;i >= 0 ; --i)
  160. cout<<" "<<s[T[Tp[i]].id] ;
  161. }
  162. else
  163. {
  164. cout<<s[T[Tp[0]].id] ;
  165. for(int i = 1 ;i < Tp.size() ; ++i)
  166. cout<<" "<<s[T[Tp[i]].id] ;
  167. }
  168. }
  169. else
  170. {
  171. cout<<s[T[Tp[0]].id] ;
  172. for(int i = 1 ;i < Tp.size() ; ++i)
  173. cout<<" "<<s[T[Tp[i]].id] ;
  174. }
  175. cout<<endl ;
  176. }
  177. }
  178. return 0 ;
  179. }


文章来源: blog.csdn.net,作者:Linux猿,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/nyist_zxp/article/details/41245301

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。