UVa 1252 - Twenty Questions（记忆化搜索，状态压缩dp） - c++编程基础

TOP

UVa 1252 - Twenty Questions（记忆化搜索，状态压缩dp）

2015-07-24 05:36:18 来源: 作者: 【大中小】浏览:5次

题目链接：uva 1252

题意:
有n个长度为m的二进制串，每个都是不同的。
为了把所有字符串区分开，你可以询问，每次可以问某位上是0还是1。
问最少提问次数，可以把所有字符串区分开来。

思路来源于：点击打开链接
思路： m很小，可以考虑状态压缩。 dp[s1][s2]表示询问的状态为s1时，此时能猜到状态包含s2时最小需要的步数。当询问的几位=s2的二进制串小于2时就能区分出来了，dp[s1][s2]=0；不能区分则再询问一次，s1|=(1< 代码：

#include 
   
    
#include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
          #include 
          
            #include 
           
             #include 
            
              #include 
             
               #define maxn 1005 #define MAXN 1000005 #define mod 100000000 #define INF 0x3f3f3f3f #define pi acos(-1.0) #define eps 1e-6 typedef long long ll; using namespace std; int n,m,ans,tot,flag; char s[150][15]; int dp[1<<11][1<<11],mp[150]; int dfs(int s1,int s2) { if(dp[s1][s2]


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：oc中如何调用c++的方法	下一篇：UVA 11237 - Halloween treats(鸽..